問題文

DIVCO 君は, 正方形のチップを 1 枚持っている. 彼は, このチップを切って小さなチップに分割し, 重ねてタワーにしようと考えた.

具体的には, DIVCO 君は次の処理を N 回繰り返すことによりチップを分割する.

• 現在持っているチップをそれぞれ 4 等分し, 4 枚のより小さなチップを得る.

さて, N 回の処理を終えたとき, DIVCO 君は何枚のチップを持っているか？

制約

• N は 1 以上 5 以下の整数

入力例 1

1

出力例 1

4

処理を 1 回行うと, チップは 4 枚に分割される.

入力例 2

2

出力例 2

16

2 回目の処理では, 1 回目の処理で得られた 4 枚のチップがそれぞれ 4 等分され, チップの枚数は合計で 4 \times 4 = 16 枚となる.

問題文

写真撮影のプロの DISTO 君は, 黒い正方形のチップの写真を撮り, 下の図のように映った.

ただし, 茶色の枠の内側のみが実際の写真である. また, 緑色の矢印で指した箇所ではチップの頂点が写真の端と接しており、写真の辺を 2 等分している.

DISTO 君は, 写真をより小さな画像データに圧縮しようと思った. 圧縮後の画像データは, N \times N のマス目として表される.
圧縮後の画像データの各マスの色は次のように決まる: 写真の縦と横をそれぞれ N 等分して N \times N 個の領域に分割したとき, 完全に黒であるような領域に対応するマスのみが黒, そうでないマスは白である.

圧縮後の画像データを構成する N^2 個のマスのうち, 黒いマスは何個あるか？

制約

• N は 2 以上 100 以下の整数

入力例 1

5

出力例 1

5

写真は下図のように 5 \times 5 個の領域に分割され, このうち完全に黒であるような領域の個数は 5 個である.

入力例 2

10

出力例 2

40

写真は 10 \times 10 個の領域に分割され, そのうち完全に黒であるような領域の個数は 40 個である.

入力例 3

21

出力例 3

181

写真は 21 \times 21 個の領域に分割され, そのうち完全に黒であるような領域の個数は 181 個である.

問題文

高橋君の飼い犬の BISCO は, ディスコ株式会社で働いている. ある日, BISCO は 10 年間の功績を認められ, 社長の WISCO からプレゼントとして正方形のチップを 100 枚渡された.

BISCO は, これらのチップを以下のように 10 行 10 列に並べた.

ここで, 上から a 番目, 左から b 番目にあるチップを「チップ (a, b)」と表す.

さて, BISCO はこれらのチップに以下のようにして整数を書き込むことにした.

• まず, 数列 P = (P_1, P_2, P_3, ..., P_{10}) と Q = (Q_1, Q_2, Q_3, ..., Q_{10}) を決める. これらの項の値はすべて正の整数でなければならない.
• 次に, 各チップ (i, j) に整数 P_i \times Q_j を書き込む.
• このとき, チップに書き込む整数はすべて 1 以上 N 以下でなければならない. この条件が満たされたときのみ, 書き込みが成功する.

BISCO は, 書き込みが成功するような数列 P, Q の決め方が何通り存在するかに興味を持った.
彼のために, 書き込みが成功するような (P_1, P_2, P_3, ..., P_{10}, Q_1, Q_2, Q_3, ..., Q_{10}) の組合せとして考えられるものの個数を 1 \ 000 \ 000 \ 007 で割った余りを求めなさい.

制約

• N は 1 以上 100 \ 000 以下の整数

入力例 1

1

出力例 1

1

N = 1 のとき, 数列 P, Q のすべての項の値を 1 とするしかない. この場合, すべてのチップに 1 \times 1 = 1 が書き込まれ, 書き込みは成功する.

入力例 2

2

出力例 2

2047

入力例 3

3

出力例 3

118097

入力例 4

116

出力例 4

795526989

求めたい組合せの個数を 1 \ 000 \ 000 \ 007 で割った余りを出力せよ.

問題文

高橋君の飼い犬の BISCO は, ディスコ株式会社に 29 年務め, ついに退職の時を迎えた. 彼は会社に大きく貢献したため, 社長の WISCO から「黄金の正方形チップ」をプレゼントされた.

このチップには, 秘密の整数 N がデータとして入っており, BISCO は N が 1 以上 10^{12} 以下の整数であることを知っている.
しかし, この整数 N の実際の値は社長しか閲覧することができない.

それでも BISCO が秘密の整数を知りたがったので, 社長の WISCO は, 以下の値をヒントとして与えた.

• a_2, a_3, a_4, ..., a_{30} の 29 個の値.
• ただし, a_i は「整数 N を i 進数で表したときの各位の桁の和」である.

例えば, N = 1123 のとき, N を 4 進数で表すと 101203 となるため, a_4 = 1 + 0 + 1 + 2 + 0 + 3 = 7 となる.

BISCO のために, ヒントをもとにして秘密の整数 N を当てなさい.
ただし, 秘密の整数としてあり得る数が複数存在する場合はそのうちのどれを出力してもよく, そのような数が存在しない場合は invalid と出力しなさい.

制約

• a_2, a_3, a_4, ..., a_{30} はすべて 1 以上 500 以下の整数

入力例 1

3
5
4
1
5
7
4
9
7
5
3
13
12
11
10
9
8
7
6
5
4
3
2
1
25
25
25
25
25

出力例 1

25

N = 25 は, 秘密の整数としてあり得る数である.

• 25 を 2 進数で表すと 11001 となり, 各位の桁の和は 3 で, これは a_2 に等しい.
• 25 を 3 進数で表すと 221 となり, 各位の桁の和は 5 で, これは a_3 に等しい.

この性質は, a_4 から a_{30} までについても同じように満たされる.

入力例 2

500
30
33
36
39
42
45
48
51
54
57
69
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111

出力例 2

invalid

a_2 = 500 に注目する.
2 進数で表したときに各位の桁の和が 500 となるような最小の正の整数は 2^{500} - 1 で, これは秘密の整数 N の値の上限である 10^{12} を大きく超える.
したがって, 秘密の整数としてありうる数は存在しない.

入力例 3

23
27
35
31
36
29
55
63
23
61
49
47
86
69
86
111
63
113
63
71
104
93
95
95
111
125
167
111
111

出力例 3

201811232111

201811232111 は, 秘密の整数としてあり得る数である.

入力例 4

14
25
20
13
31
41
30
49
2
61
68
65
67
65
56
65
65
83
27
81
107
101
106
41
126
93
83
121
108

出力例 4

invalid

秘密の整数は 10^{12} 以下であることに注意せよ. (この条件を除けば, 1000000000001 が秘密の整数としてあり得る数となる.)