19170번 - Denominations 다국어

문제

Greedy Smurf is opening a new shop in Smurf Village. Smurfs use coins with four denominations: 1, 5, 10 and 25 SmurfCoins. Write a program that will compute for Greedy the number of ways that he can give change of $n$ SmurfCoins.

Output the number of different ways of giving change modulo 10ドル^9 + 7$. Two ways of giving change are considered different if they differ in the amount of used coins of some denomination.

입력

First and only input line contains $n$ (1ドル \leq n \leq 10^{18}$) -- the amount of change.

출력

Output the number of different ways of giving change modulo 10ドル^9 + 7$. Two ways of giving change are considered different if they differ in the amount of used coins of some denomination.

제한

힌트