Problem description

Rozważmy choinki w ASCII art zbudowane z dowolnej liczby trójkątów równoramiennych o parami różnych wysokościach, czyli podobnie jak w zadaniach Rysowanie choinki i Zgadywanie choinki, ale z następującymi różnicami:

• choinka może się składać z dowolnej liczby trójkątów, a nie zawsze trzech,
• kolejne trójkąty nie muszą się różnić wysokością o 1,
• zapominamy o pniu choinki.

Przykładową sensowną choinką spełniającą powyższe warunki jest taka:

    *
   ***
  *****
    *
   ***
  *****
 *******
*********

Powyższa choinka składa się z 34 gwiazdek. Jest to jedyna choinka, która ma dokładnie tyle gwiazdek.

Ile jest różnych choinek składających się z dokładnie N gwiazdek? Napisz program, który wczyta wartość N, wyznaczy liczbę uogólnionych choinek składających się z N gwiazdek i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę gwiazdek, z których składa się choinka.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć reszta z dzielenia przez 10⁹ + 7 liczby sposobów zbudowania uogólnionej choinki z dokładnie N gwiazdek.

Ograniczenia

1 ≤ N ≤ 100 000.

Przykład

34

1

3

0

25

2