No.492 IOI数列

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 75
作問者 : square1001square1001 / テスター : e869120e869120

2 ProblemId : 1283 / 出題時の順位表

問題文

あるとき, lttさんは, あるコンテストで101位を取ってギリギリ賞金を逃がしてしまいました。

しかし, いつもポジティブなlttさんは, 次のように考えました。

「『101』・・・これはIOIを表している。これはIOIに行けるような実力を持っているということだ!」

そこで, 彼は次のような「IOI数列」という数列を定義し, 自信を高めようとしました。

IOI数列は, $1, 101, 10101, 1010101, 101010101, 10101010101,\dots$ と続く数列です。

彼は, この数列が$a_1=1, a_i=100a_{i-1}+1$となっていることに気付きました。

しかし, これを速く解く方法を彼は知らなかったので, 友達であるあなたに手伝ってもらうことにしました。

整数$N$が与えられます。そのとき, IOI数の第N項を$1000000007$で割った余りと$101010101010101010101$で割った余りを求めなさい。

入力

$N$

1行目に整数$N (1≦N≦10^{18})$が与えられる。

出力

1行目に$a_N$ mod $1000000007$を出力しなさい。

2行目に$a_N$ mod $101010101010101010101$ を出力しなさい。

最後に改行を忘れないこと。

サンプル

サンプル1
入力
3
出力
10101
10101

$a_3=10101$です。

サンプル2
入力
7
出力
101003031
1010101010101

$a_7=1010101010101$であり, $a_7$ mod $1000000007 = 101003031$ となります。

サンプル3
入力
101
出力
963727330
101

$a_{101}$ mod $101010101010101010101 = 101$ となります。

提出ページヘ