No.492 IOI数列
タグ : / 解いたユーザー数 129
作問者 : square1001 / テスター : e869120
問題文
あるとき, 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$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。