Tteokpire

Time limit1sMemory limit128 MB

Summary

Count the number of ways to write N as an ordered sequence of one or more positive integers; equivalently, count compositions of N, modulo 1e9+7, for N up to 1e12.

Level: Hard9 of 10
Topics: Combinatorics, Math, Number theory, Divide and conquer
Solved: No attempts yet

Problem

A tteokpire keeps from aging by eating tteokguk, the Korean rice cake soup.

A tteokpire grows one year older for every bowl of tteokguk it eats. Digestion finishes the moment a bowl goes down, so a tteokpire eats as many bowls as it wants in one day. No matter how much it ate before, a tteokpire that eats no tteokguk on some day ends its life that day.

A tteokpire starts at age 0, and at the end of every day its age grows by the number of bowls it ate that day. Didi wants to count how a tteokpire that ended its life at age $N$ could have aged. Two lives count as different if the tteokpire lived a different number of days, or if it ate a different number of bowls on some day.

For $N$ equal to 3 there are four lives.

3 bowls on day 1, 0 bowls on day 2
1 bowl on day 1, 2 bowls on day 2, 0 bowls on day 3
2 bowls on day 1, 1 bowl on day 2, 0 bowls on day 3
1 bowl on day 1, 1 bowl on day 2, 1 bowl on day 3, 0 bowls on day 4

The count grows very large as $N$ grows. Write a program that counts the ways a tteokpire that ended its life at age $N$ could have aged.

Input

The first line contains an integer $N$ . ( $0 \le N \le 10^{12}$ )

Output

On the first line, print the number of ways of aging, modulo $10^9 + 7$ .

Examples1

Example 1
Input
```
3
```
Expected output
```
4
```