1. Toľko možností...

Luxusko si kúpil novú knižku s názvom Kvantové Správanie a Paralelizmus. Dozvedel sa z nej, že (vraj) každé naše rozhodnutie spôsobí vznik paralelných vesmírov, ktoré sú všetky veľmi podobné a líšia sa iba v tom jednom rozhodnutí a v jeho následkoch.

Napríklad, keď sa ráno rozhodnete, či vstanete alebo len zaklapnete budík a pospíte si o 10 minút dlhšie, vzniknú dva paralelné vesmíry. V jednom vesmíre spíte ďalej a pravdepodobne zmeškáte prvú hodinu v škole, v druhom pekne vstanete a prídete do školy načas.

Podľa knižky pri každom takomto rozvetvení vesmíru nastane veľmi slabé chvenie v okolí toho, kto urobil rozhodnutie. Keď sa vesmír rozdvojí, chvenie je zvyčajne také slabé, že sa nedá zachytiť. Je však možné, že ak urobíme rozhodnutie, ktoré má za následok vznik miliardy paralelných vesmírov, spomenuté chvenie sa stane merateľným a celá hypotéza by sa tak dala dokázať.

Luxusko teda zobral svoju obrovskú zbierku mincí s hodnotami 1, 5, 10 a 20 centov a vybral sa do obchodu. Kúpi si v obchode niečo v hodnote \(n\) centov, urobí rozhodnutie ako túto vec zaplatí pomocou svojich mincí a napokon svojim vreckovým seizmografom odmeria chvenie.

Potrebuje však namerané výsledky s niečim porovnať, preto chce presne vedieť, koľko vesmírov malo vzniknúť – čiže koľkými spôsobmi sa dá zaplatiť daná suma \(n\).

Úloha

Máte danú cenu \(n\). Zistite, koľkými spôsobmi sa dá táto cena zaplatiť mincami, ktoré majú hodnoty 1, 5, 10 a 20 centov. Dva spôsoby platenia sú rôzne, pokiaľ použijú iný počet kusov nejakej mince.

Výsledok vypíšte modulo \(10^9+7\).

Formát vstupu

Na vstupe je jeden riadok s celým číslom \(n\) (\(1\leq n\leq 10^{18}\)).

Formát výstupu

Vypíšte počet spôsobov, ktorými sa dá zaplatiť suma \(n\) pomocou mincí s hodnotami 1, 5, 10 a 20 modulo \(10^9+7\).

Príklady

Input:

14

Output:

4

Input:

30

Output:

20

Input:

7

Output:

2

Napríklad cenu \(14\) môžeme zaplatiť týmito štyrmi spôsobmi: \(10+1+1+1+1\), \(5+5+1+1+1+1\), \(5+1+1+1+1+1 + 1+1+1+1\) a \(1+1+1+1+1 + 1+1+1+1+1 + 1+1+1+1\)