No.557 点対称

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 89
作問者 : butsuri_0523butsuri_0523 / テスター : はむこはむこ

1 ProblemId : 1789 / 出題時の順位表

問題文

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行に出力し、最後に改行してください。

サンプル

サンプル1
入力
2
出力
4

11,69,88,96の4つです。

サンプル2
入力
3
出力
12

101,111,181,609,619,689,808,818,888,906,916,986 の12個です。

サンプル3
入力
57
出力
237171741

サンプル4
入力
864
出力
926092950

サンプル5
入力
1
出力
2

1,8の2つです。

提出ページヘ