Problem G
Sammaeining
Languages
en
is
Sammi’s favorite number is $7$. He is so infatuated by it that everything he does revolves around the number $7$. Sammi is also a Hackintosh confectionary enthusiast.
Sammi recently got a box of Hackintosh confectioneries with $n$ pieces. Each piece was labeled with a unique number between $1$ and $n$. Sammi eats some assortment of pieces if and only if the sum of all of the pieces ends in $7$. Sammi wants to know how many different possible assortments are edible.
Input
The input is one line, the integer $n$, the size of the box.
Output
The output is one line, amount of different possible edible assortments. Since the answer can be very large, you should output it modulo $10^9+7$.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$1 \leq n \leq 20$ |
|
2 |
25 |
$1 \leq n \leq 10^6$, $n$ is a multiple of 10 |
|
3 |
25 |
$1 \leq n \leq 10^6$ |
|
4 |
15 |
$1 \leq n \leq 10^{15}$, $n$ is a multiple of 10 |
|
5 |
15 |
$1 \leq n \leq 10^{15}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
18 |
26212 |
