Xét hàm số ~f: \mathbb{Z}^+ \to \mathbb{Z}^+~ xác định bởi ~f(0) = 1~ và

~f(2n) = f(n-1)+f(n), \, f(2n+1) = f(n), \, n \le 1.~

Cho biết rằng mỗi số hữu tỷ ~p/q~ với ~p,q~ nguyên dương thì luôn có duy nhất một cách biểu diễn dưới dạng ~\frac{f(n)}{f(n+1)}.~ Xem hình minh họa bên dưới:

Yêu cầu đặt ra là cho trước các số ~p,q~, hãy tìm số ~n~ thỏa mãn biểu diễn trên.

Input

Hai số nguyên dương ~p,q~ với ~1 \le p,q \le 10^5.~

Output

Một số nguyên duy nhất là đáp số của bài toán. Kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Sample input 1

2 3

Sample output 1

5

Sample input 2

1 4

Sample output 2

7

Các Ví dụ 1, 2 có thể dễ dàng kiểm tra được trên sơ đồ đã cho.

Có ~50\%~ test của đề ứng với các số ~p,q \le 100~.