URI Online Judge | 1906
# Collatz Passwords

**Timelimit: 2**

By Leandro Zatesko, UFFS Brazil

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 **a**_{0}, **a**_{1}, **a**_{2}… such that **a**_{0} = **X** and, for each **i** > 0, **a _{i}** =

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

The single input line consists of two positive integers **N** and **K** (**N**, **K** ≤ 10^{7}).

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 |