問題一覧 > 通常問題

No.557 Point Symmetry

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 183
作問者 : butsurizuki / テスター : はむこ
お気に入りにしたユーザー ProblemId : 1789 / 自分の提出
問題文最終更新日: 2026-06-26 06:06:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 171 (順位表) の他の問題:

Problem Statement

B-kun saw the number "90106" and had a thought.
"Wouldn't this remain 90106 even if rotated 180 degrees around its center?"
Find how many $N$-digit numbers are point-symmetric in this way about the center of the number. (Here, numbers with 0 in the leading position are not counted.)
Assume that 1, 8, and 0 keep the same shape when rotated 180 degrees, 6 coincides with 9 when rotated 180 degrees, 9 coincides with 6 when rotated 180 degrees, and any other digit does not coincide with any digit when rotated 180 degrees. Since the answer can be very large, find the remainder when it is divided by 1000000007.

Although the shape of 1 appears different after a 180-degree rotation, it is regarded as identical.

Input

$N$

$N$ is given on one line.
・Constraints
$1 \le N \le 10^{18}$

Output

Output the answer on one line, followed by a newline.

Sample

Sample 1
Input
2
Output
4

There are 4 such numbers: 11, 69, 88, 96.

Sample 2
Input
3
Output
12

There are 12 such numbers: 101, 111, 181, 609, 619, 689, 808, 818, 888, 906, 916, 986.

Sample 3
Input
57
Output
237171741

Sample 4
Input
864
Output
926092950

Sample 5
Input
1
Output
2

There are 2 such numbers: 1, 8.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。