ノート

問題文

コンピュータが登場する前、計算する道具といえば「そろばん」だった。
今回は、そのそろばんがテーマの問題である。

一般的なそろばんは、一列だけ見ると、５つ珠があり０〜9まで表すことができる。

これは、１列に串刺し状の上部１つの珠と下部４つの珠に分けて、
下部の動いている珠の数、上部の動いている珠分さらに5を足すという数の表現方法を行う。
つまり上部は、下部の数の繰り上がり数と見ることができる。
参考: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
（そろばんを知らない方はごめんなさい。。）

このとき、Ursaは特殊なそろばんを思いついた。
一列に使える珠の合計を$N$個とし、上部と下部に使える珠の数は、合計で$N$個であれば自由に決めることができるとする。
この時、一列分で表現できる最大の数を求めてください。

ただし、表現方法としてできるのは、それぞれの珠の上げ下げの状態のみで判断するとする。
中途半端に動かすなどできないとし、上部・下部はそれぞれ連続に並んでいる珠なので３つ目が動くなら、１つめ２つ目も連動して動くような機構であるとする。
また、0から最大の数まで一意的な表現ができるとする。

入力

$N$

入力は整数で与えられる。

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

出力

一列分で表現できる最大の数を求めて出力してください。
桁が大きくなるので $1000007=10^6+7$で割った余りを求めてください。
（オーバーフロー回避目的なためであり、多倍長使える方は、最後にmod取るだけで十分です。）
最後に改行してください。

サンプル

5

11

19

109

1000000

250007