시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 512 MB305522.727%

문제

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.

예제 입력 1

14

예제 출력 1

4