Числа Фибоначчи

Числа Фибоначчи - это последовательность целых чисел, заданная рекурентным соотношением:

F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n ≥ 2.

Ваша задача - найти наибольший общий делитель двух чисел Фибоначчи.

Input

Во входном файле два числа i и j (1 ≤ i, j ≤ 10^6) - номера чисел Фибоначчи.

Output

В выходной файл выведите остаток от деления наибольшего общего делителя чисел F_i и F_j на 10^9.

Examples