BABBA

Interview

Time limit1sMemory limit128 MB

Summary

Starting from A and rewriting each B as BA and each A as B, count the As and Bs after K presses.

Level: Easy3 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Sanggeun found a strange machine while walking down the street. The machine has one very large screen and a single button.

When he first saw it, the screen showed a single A. He pressed the button and the letter became B. Another press made it BA, the next made it BAB, and the next made it BABBA. Sanggeun figured out the rule: every press rewrites each B on the screen as BA, and each A as B.

Find how many A's and how many B's are left on the screen after the button is pressed $K$ times.

Input

The first line contains $K$ ( $1 \le K \le 45$ ).

Output

Print the number of A's and the number of B's on the first line, separated by a single space.

Examples3

Example 1
Input
```
1
```
Expected output
```
0 1
```
Example 2
Input
```
4
```
Expected output
```
2 3
```
Example 3
Input
```
10
```
Expected output
```
34 55
```