問題文

bくんは、"90106"という数値を見てあることを考えました。
「これは真ん中を軸に180度回転させても90106のままなのでは」
このように、数値の真ん中を軸にして点対称になる$N$桁の数がいくつあるか求めてください。(ここで、一番先頭の位に0が来る数はカウントしません。)
1,8,0は180度回転させても同じ形、6は180度回転させると9に重なり、9は180度回転させると6に重なり、他の数字は180度回転させても他のどの数字とも重ならないとします。 解は非常に大きくなる場合があるので1000000007で割った余りを求めてください。

180度回転させると1の形が違っているように見えるが、同一にみなすとする。

入力

$N$

$N$が1行に与えられます。
・制約
$1\le N\le {10}^{18}$

出力

解を1行に出力し、最後に改行してください。

サンプル

2

4

3

12

57

237171741

864

926092950

1

2