問題文

あるとき, 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$ を出力しなさい。

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

サンプル

3

10101
10101

7

101003031
1010101010101

101

963727330
101