Let's consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn't contain two successful zeroes.

Example: 1010230 is a valid 7-digit number 1000198 is not a valid number 0001235 is not a 7-digit number, it is a 4-digit number.

Given two numbers N and K, you are to calculate an amount of valid K based numbers, contaning N digits.

You may assume that 2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.

Input two decimal numbers N and K

Output The result in decimal notation.

Sample Input 2 10

Sample Output 90

我在网上找的，懂的就一起来讨论讨论并做做吧

这里人多相信高手也不少

哦这题没什么意思知道递推公式就简单了还是做这道吧

Two Nikifors play a funny game. There is a heap of N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins. You are to write a program that determines winner assuming each Nikifor does its best.

Input

An input contains the only positive integer number N (condition N <= 10²⁵⁰ holds).

Output

The first line of an output file should contain 1 in the case the first Nikifor wins and 2 in case the second one does. If the first Nikifor wins the second line should contain the minimal number of stones he should take at the first move in order to guarantee his victory.

Sample Input

8

Sample Output

12

1，2，3的我想很多人都玩过一个类似的游戏抢30

但是1，2，4，8呢？