TopCoder

Thumb mikasa mikoto furikae
Omelet
$\Huge\mathcal A=(Q,\Sigma,\delta:Q\times\Sigma\to Q,s\in Q,F\subseteq Q)$

User's AC Ratio

81.4% (35/43)

Submission's AC Ratio

30.3% (53/175)

Description

在你算完病毒個數模3的餘數之後(看這裡),這飛行船繼續在空中徘徊。恐怖分子並沒有要妥協的意思,而為了不讓病毒擴散至地面,這艘飛船不能降落。

從病毒開始擴散,已經過了$i$分鐘。飛船上已經只剩你一個人了(其它人已因致命的肺噬病毒而死亡,然而你身上帶有某種神奇的抗體,可能是你算出了病毒個數模3的緣故吧)。盡責的船長在斷氣前的那剎那開啟了自動飛航模式,讓飛船得以繼續在空中徘徊。

這時,從你背後傳來急促的腳步聲。當你心想著「原來還有倖存者啊」回頭看時,你發現恐怖份子的同夥正拿著棒子朝著你的頭一揮………

等你醒來的時候,你發現你被拷起來,手腳無法動彈了。你抬頭看了一下時鐘,「啊…從病毒開始擴散已經過了$j$分鐘啊…」
這時恐怖份子拿著槍指著你的頭:「你是怎麼弄到解藥的?快說!只要解藥存在,我輩(?)征服世界的野望就…」

在這大難臨頭的當下,你唯一想做的事情是……
計算$F_i$和$F_j$的最大公因數!

註:注意
(1) $F_1=1, F_2=2$
(2) $F_{n+2}=F_{n}+F_{n+1}\quad\forall n\in\mathbb{N}$(意思是「對於所有正整數n」。)

Input Format

輸入只有一行,含有兩個正整數$i,j\leq 10^ {18}$。
為了維持故事中$i$和$j$的先後順序,$i<j$。

子任務(測資) 額外限制 分數
1 (0~4) $i< j\leq 80$ 3
2 (5~9) $i< j\leq 10^ 3$ 12
3 (10~14) $i< j\leq 10^ 6$ 37
4 (15~19) 無限制 48

Output Format

請輸出一個數,代表$F_i$和$F_j$的最大公因數。因為答案有點大,請模$10^ 9+7$後再輸出。

Sample Input

5 8

Sample Output

2

Hints

$F_5=8, F_8=34$
兩數的最大公因數是2

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pF

Subtasks

No. Testdata Range Score
1 0~4 3
2 5~9 12
3 10~14 37
4 15~19 48

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 100 65536 262144 1
1 100 65536 262144 1
2 100 65536 262144 1
3 100 65536 262144 1
4 100 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 100 65536 262144 3
11 100 65536 262144 3
12 100 65536 262144 3
13 100 65536 262144 3
14 100 65536 262144 3
15 100 65536 262144 4
16 100 65536 262144 4
17 100 65536 262144 4
18 100 65536 262144 4
19 100 65536 262144 4