cho.sh

Tteokpire

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.

Hard9CombinatoricsMathNumber theoryDivide and conquerNo attempts yetTime limit1sMemory limit128 MB

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 NN 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 NN 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 NN grows. Write a program that counts the ways a tteokpire that ended its life at age NN could have aged.

Input

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

Output

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