2. Toľko možností v Amerike

Táto úloha je mierne ťažšou verziou úlohy číslo 1, “Toľko možností”

Po úspechu s pokusmi doma sa rozhodol Luxusko preskúmať, ako sa správa delenie vesmíru na inom mieste. Vycestoval do ďalekých Spojených štátov amerických a pokus zopakoval. V USA však majú mince s inými hodnotami, namiesto 20 centoviek musel použiť 25 centovky.

Úloha

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

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 25 modulo \(10^9+7\).

Príklady

Input:

14

Output:

4

Input:

30

Output:

18

Input:

7

Output:

2