Dãy số Fibonacci là một dãy số đặc biệt trong đó mỗi số là tổng của hai số trước đó. Dãy số Fibonacci được định nghĩa như sau:

\[ \begin{align*} F(0) &= 0, \\ F(1) &= 1, \\ F(n) &= F(n-1) + F(n-2) \quad \text{cho } n \geq 2. \end{align*} \]

Cho hai số nguyên \(A\) và \(B\) yêu cầu hãy tính \(GCD(F(A), F(B))\). Ở đây \(GCD(a, b)\) có nghĩa là ước chung lớn nhất của hai số \(a\) và \(b\). Vì số có thể rất lớn nên hãy lấy kết quả chia lấy dư cho \(1000000007\).

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(A\) và \(B\) \((1 \leq A, B \leq 10^6)\).

OUTPUT FORMAT

In ra một số nguyên duy nhất là kết quả của bài toán.

Rằng buộc

Subtask 1 (70% số điểm): \(A, B \leq 50\) ;

Subtask 2 (30% số điểm): Không có ràng buộc nào thêm.

Ví dụ:

Input

6 9

Output

2

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House