一台文字屏最初只显示一个字母 A。小泽每按一次按钮，屏幕会同时完成下面两种替换：

• 所有 A 都变成 B；
• 所有 B 都变成字符串 BA。

“同时替换”表示本轮新产生的字母不会在同一轮再次变化。连续按下 $K$ 次后，统计面板只显示最终字符串中 A 与 B 的数量，而不需要保存整段越来越长的字符串。

输入格式

一行一个整数 $K$，表示按钮按下的次数。

输出格式

一行两个整数，依次表示最终字符串中 A 和 B 的数量。

3

1 2

1

0 1

45

701408733 1134903170

样例解释

初始为 A。三次变化为 B、BA、BAB，最终有 $1$ 个 A 和 $2$ 个 B。

数据范围与约定

• $1\le K\le45$