Letter Transformation and Fibonacci Count

Mirko discovered a huge screen that initially displayed a single character \(\texttt{A}\). Beside the screen was a button. When he pressed the button for the first time, the screen changed to \(\texttt{B}\). With each subsequent press, the transformation rule was applied to every character on the screen: every \(\texttt{B}\) becomes \(\texttt{BA}\) and every \(\texttt{A}\) becomes \(\texttt{B}\). Thus, the sequence of the screen's content evolves as follows: \(\texttt{A} \to \texttt{B} \to \texttt{BA} \to \texttt{BAB} \to \texttt{BABBA} \to \cdots\).

After pressing the button \(k\) times, Mirko wants to know how many \(\texttt{A}\)s and \(\texttt{B}\)s are present on the screen.

Hint: If you denote by \(A_k\) the number of \(\texttt{A}\)s and by \(B_k\) the number of \(\texttt{B}\)s after \(k\) presses, then by observing the transformation, you may notice that for \(k \geq 1\):

[ A_k = B_{k-1}, \quad B_k = A_{k-1} + B_{k-1}, ]

These recurrences reveal that the counts follow the Fibonacci sequence (with appropriate initial conditions). Specifically, if we define \(F_1 = 1, F_2 = 1\), then for \(k \geq 1\), we have \(A_k = F_{k-1}\) and \(B_k = F_{k}\). Note that when \(k = 0\), the screen shows \(\texttt{A}\), i.e. \(A_0 = 1, B_0 = 0\).

inputFormat

The input consists of a single integer \(k\) (\(0 \le k \le 10^5\)), representing the number of times the button has been pressed.

For example:

3

outputFormat

Output two integers separated by a space: the first is the number of \(\texttt{A}\)s and the second is the number of \(\texttt{B}\)s on the screen after \(k\) presses.

For the sample input above, the correct output is:

1 2

sample

0

1 0