Denominations

아직 제출이 없습니다시간 제한0.5초메모리 제한512 MB

문제 설명

예제1

문제

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.