No.492 IOI Sequence
タグ : / 解いたユーザー数 137
作問者 :
square1001
/ テスター :
e869120
Problem Statement
One day, ltt placed 101st in a contest and narrowly missed out on the prize money.
However, ltt, who is always positive, thought as follows.
"'101'... this stands for IOI. It means I have the ability to go to the IOI!"
So, he defined a sequence called the "IOI sequence" as follows, trying to boost his confidence.
The IOI sequence is the sequence that goes $1, 101, 10101, 1010101, 101010101, 10101010101,\dots$.
He noticed that this sequence satisfies $a_1=1, a_i=100a_{i-1}+1$.
However, he did not know a fast way to solve this, so he decided to ask you, his friend, for help.
An integer $N$ is given. Find the remainder when the Nth term of the IOI numbers is divided by $1000000007$ and the remainder when it is divided by $101010101010101010101$.
Input
$N$
The first line contains an integer $N (1≦N≦10^{18})$.
Output
On the first line, output $a_N$ mod $1000000007$.
On the second line, output $a_N$ mod $101010101010101010101$.
Do not forget the newline at the end.
Sample
Sample 1
Input
3
Output
10101 10101
$a_3=10101$.
Sample 2
Input
7
Output
101003031 1010101010101
$a_7=1010101010101$, and $a_7$ mod $1000000007 = 101003031$.
Sample 3
Input
101
Output
963727330 101
$a_{101}$ mod $101010101010101010101 = 101$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。