Șirul numerelor Fibonacci se definește în felul următor:
fib(0) = 0 fib(1) = 1 fib(i) = fib(i-1) + fib(i-2), pentru orice i > 1
Cerinţă
Determinați valoarea celui mai mare divizor comun (cmmdc) a doi termeni din șir, specificați prin pozițiile lor N și M. Termenul cu poziția N este fib(N), iar cel cu poziția M este fib(M). Afișați restul (modulo) acestei valori la împărțirea prin 1000333.
Date de intrare
Programul citește de pe prima linie din fișierul fibgcd.in două numere naturale N și M. Cele două numere reprezintă pozițiile termenilor din șir.
Date de ieşire
Programul scrie pe prima linie din fișierul fibgcd.out valoarea cmmdc(fib(N), fib(M)) modulo1000333.
Restricţii
0 ≤ N, M ≤ 1018
Pentru teste în valoare de 20% din punctajul maxim, 0 ≤ N, M ≤ 80
Pentru teste în valoare de 50% din punctajul maxim, 0 ≤ N, M ≤ 20000