Denominations

Time limit0.5sMemory limit512 MB

Summary

Count the number of ways to make change for n SmurfCoins using denominations 1, 5, 10, 25, modulo 10^9+7, where n can be as large as 10^18.

Level: Medium7 of 10
Topics: Math, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

Greedy Smurf is opening a new shop in Smurf Village. Smurfs use coins in four denominations: 1, 5, 10 and 25 SmurfCoins. Write a program that computes, for Greedy, the number of ways 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 different if they use a different number of coins of some denomination.

Input

The first and only input line contains $n$ ( $1 \leq n \leq 10^{18}$ ), the amount of change.

Output

Output the number of different ways of giving change modulo $10^9 + 7$ . Two ways of giving change are different if they use a different number of coins of some denomination.

Examples1

Example 1
Input
```
14
```
Expected output
```
4
```