Lucky numbers without consecutive fours
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Today everyone is celebrating Lucky Numbers Day!
One of the traditional activities on this day is checking various properties of lucky numbers.
Everyone knows that a number is lucky if its decimal representation contains only the digits 4 and 7. Marichka considers a lucky number wonderful if it does not contain two fours in a row.
And what is the sum of all wonderful numbers whose decimal representation contains at most \(n\) digits? Since this value can be very large, find the remainder of the division of the answer by \(10^9+7\).
Input
The single line contains a single integer \(n\) – the maximum length of the decimal representation of a wonderful lucky number.
Output
In the single line, output the sum of wonderful lucky numbers modulo the prime number \(10^9 + 7\).
Constraints
\(1 \le n \le 10^{18}\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 | 209 |
Notes
The only lucky number of length \(\le\) 2 that is not wonderful is 44. Therefore, the sum \(=4+7+47+74+77=209\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|