Problem G
Sammaeining
Languages
en
is
Hann Sammi hefur mikinn áhuga á tölunni $7$. Svo mikinn áhuga að allt sem hann gerir byggist á tölunni $7$. Sammi er líka mikill áhugamaður um Hackintosh konfekt.
Nýlega fékk Sammi konfektkassa með $n$ konfektmolum. Hver konfektmoli er merktur tölu frá $1$ upp í $n$ og kemur hver tala fyrir nákvæmlega einu sinni. Sammi getur einungis borðað safn af konfektmolum ef síðasti tölustafurinn í summa þeirra er $7$. Sammi vill því vita hvað eru margar samsetningar sem eru ætar.
Getur þú hjálpað Samma að koma í veg fyrir að hann svelti?
Inntak
Inntak er ein lína með einni heiltölu $n$, fjölda konfektmola.
Úttak
Skrifaðu út eina línu með einni heiltölu, fjöldi samsetninga sem eru ætar. Þar sem svarið getur verið mjög stórt skal skrifa það út módulus $10^9 + 7$.
Stigagjöf
|
Hópur |
Stig |
Takmarkanir |
|
1 |
20 |
$1 \leq n \leq 20$ |
|
2 |
25 |
$1 \leq n \leq 10^6$, $n$ er margfeldi af 10 |
|
3 |
25 |
$1 \leq n \leq 10^6$ |
|
4 |
15 |
$1 \leq n \leq 10^{15}$, $n$ er margfeldi af 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 |
