TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

79.4% (27/34)

Submission's AC Ratio

30.6% (45/147)

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

For Testdata: 0 ~ 4, Score: 3
For Testdata: 5 ~ 9, Score: 12
For Testdata: 10 ~ 14, Score: 37
For Testdata: 15 ~ 19, Score: 48
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 100 65536 65536
1 100 65536 65536
2 100 65536 65536
3 100 65536 65536
4 100 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 100 65536 65536
11 100 65536 65536
12 100 65536 65536
13 100 65536 65536
14 100 65536 65536
15 100 65536 65536
16 100 65536 65536
17 100 65536 65536
18 100 65536 65536
19 100 65536 65536