URI Online Judge | 1906

Collatz Passwords

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 2

When Professor Antônio Neri, younger, knew the Collatz Conjecture, he got very fascinated. If you do not know the Collatz Conjecture yet, it states that, for any positive integer X, the Collatz sequence for X eventually reaches 1. By the way, the Collatz sequence for a positive integer X is defined as the infinite sequence a0, a1, a2… such that a0 = X and, for each i > 0, ai = ai-1 / 2 if ai-1 is even or ai = 3 × ai-1 + 1 if ai-1 is odd. For example, for X = 7, the first 20 terms of the Collatz sequence are:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1…

The Collatz Conjecture has not been proved yet, despite of existing many brilliant mathematicians in this world, as Professor Antônio Neri. He is still so fascinated by the subject that, the other day, while looking at the alarm system keypad of his house, which contains a key for each integer between 1 and N, he decided to reset his password so that the new password is a sequence of K numbers that appear consecutively in a Collatz sequence. For example, if N = 20 and K = 5, there are 11 possibilities for Professor Antônio Neri's new password:

1, 4, 2, 1, 4

2, 1, 4, 2, 1

3, 10, 5, 16, 8

4, 2, 1, 4, 2

5, 16, 8, 4, 2

6, 3, 10, 5, 16

8, 4, 2, 1, 4

10, 5, 16, 8, 4

12, 6, 3, 10, 5

16, 8, 4, 2, 1

20, 10, 5, 16, 8

Input

The single input line consists of two positive integers N and K (N, K ≤ 107).

Output

The single output line shall consist of only one integer, representing the number of possibilities for Professor Antônio Neri's new password, considering that the keypad contains a key for each integer from 1 to N and that the new password is a sequence of K numbers that appear consecutively in a Collatz sequence.

Input Samples Output Samples

20 5

11

10 1

10