题目描述
对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在hanzhoufeng有一个很“简单”问题:第n项和第m项的最大公约数是多少?但是hanzhoufeng数学太烂了,只好去问上任数学课代表么么虫....但是么么虫也不会,只好来请教你了......
输入格式
两个正整数n和m。(n,m<=10^9)
输出格式
Fn和Fm的最大公约数。
由于hanzhoufeng看了大数字就头晕,所以只要输出最后的8位数字就可以了。
样例输入
样例输出