====== 피보나치 수와 최대공약수 ======

===== 풀이 =====
  * 두가지만 알고 있으면 된다.
    * [[ps:피보나치 수#피보나치 수의 최대공약수]]에 관한 수식 gcd(f[i],f[j]) = f[gcd(i,j)] 
    * n번째 [[ps:피보나치 수]]를 O(logn)에 구하는 방법
  * 이제 그대로 구현하면 된다.  n과 m의 최대공약수 p를 구하고, p번째 피보나치수를 구한다. 둘다 O(logn)에 처리된다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11778. 피보나치 수와 최대공약수".

- Problem link: https://www.acmicpc.net/problem/11778
- Solution link: http://www.teferi.net/ps/problems/boj/11778
"""

import math
from teflib import combinatorics

MOD = 1_000_000_007


def main():
    n, m = [int(x) for x in input().split()]
    print(combinatorics.fibonacci(math.gcd(n, m), MOD))


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]]

{{tag>BOJ ps:problems:boj:골드_1}}