Simple Collatz Sequence

시간 제한1초메모리 제한1024 MB

요약

홀수 k를 k+1로 보내는 콜라츠 유사 과정에서 걸음 수가 정확히 m인 시작 정수의 개수를 구해 1000007로 나눈 나머지를 출력한다.

문제

The Simple Collatz Sequence (SCS) starting at an integer n, is defined by the formula:

S(k) = (k/2 if k is even, else (k+1))

The sequence is then n, S(n), S(S(n)), … until the value first reaches 1.

For example, starting at 11, we have:

11 -> 12 -> 6 -> 3 -> 4 -> 2 ->1

The sequence always ends at 1. (Fun Fact: The Hard Collatz Sequence sends odd k to 3*k+1. It is unknown whether that sequence always ends at 1.)

Let A(n) = number of steps in the SCS starting at n. For example, A(11) = 6.

Let C(n) = the number of integers m for which A(m) = n. For example, the integers for which A(n) = 6 are:

10, 11, 13, 24, 28, 30, 31, 64

So C(6) = 8.

Note that if n > 2m, then A(n) > m since we need to divide by 2 at least (m+1) times.

Write a program to compute C(m).

Input consists of a single line which contains a decimal integer, m, (1 ≤ m ≤ 40000), which is the value for which C(m) is to be found.

The output consists of a single line that contains the value of C(m) modulo 1000007.