Note

Problem Statement

Before computers appeared, the tool for calculation was the "soroban" (abacus).
This time, the theme of the problem is that soroban.

A typical soroban, looking at just one column, has 5 beads and can represent 0 to 9.

This works by dividing a column, strung as if on a skewer, into 1 upper bead and 4 lower beads,
and representing a number as the count of moved lower beads, plus a further 5 for each moved upper bead.
In other words, the upper part can be seen as a carry of the lower part's count.
Reference: Wikipedia
http://ja.wikipedia.org/wiki/%E3%81%9D%E3%82%8D%E3%81%B0%E3%82%93#.E5.B8.83.E6.95.B0.E6.B3.95
(Apologies to those who do not know the soroban.)

Now, Ursa came up with a special soroban.
The total number of beads usable in one column is $N$, and the numbers of beads in the upper and lower parts can be chosen freely as long as they total $N$.
Find the maximum number that can be represented by one column.

However, a representation is determined only by the raised or lowered state of each bead.
Beads cannot be moved partway, and since the beads in the upper part and in the lower part are each arranged consecutively, the mechanism is such that if the third bead moves, the first and second beads move along with it.
Also, every number from 0 to the maximum number can be represented uniquely.

Input

$N$

The input is given as an integer.

• $1 \le N \le 1000000000000000 =10^{15} $

Output

Find and print the maximum number that can be represented by one column.
Since the number becomes large, find the remainder when it is divided by $1000007=10^6+7$.
(This is to avoid overflow; if you can use arbitrary-precision integers, simply taking the mod at the end is sufficient.)
Print a newline at the end.

Sample

5

11

19

109

1000000

250007