nguồn đề: https://drive.google.com/drive/folders/1qNReFFCovMfXFB6vO8Z8XugKnr9l8TT7?usp=sharing đề 2014 bài 3

Dãy fibonacci được định nghĩa theo công thức sau :

$$f_n = \begin{cases} f_1 = f_2 = 1 \\ f_n = f_{n-1}+f_{n-2} & \text{if } n \geq 3 \end{cases}$$

dãy ~a_n~ được gọi là dãy tỷ lệ với ~f_n~ nếu: $$\frac{a_1}{f_1} = \frac{a_2}{f_2} = ... = \frac{a_n}{f_n}$$

Cho 2 số ~a_1~ và ~n~ yêu cầu tính tổng ~S~ của dãy số tỉ lệ gồm ~n~ số đầu tiên và đưa ra số dư của ~S~ chia cho ~10^9 +7~.

Input

Dòng đầu tiên chứa ~T (1 \leq T \leq 10^5) ~ Số trường hợp thử.

T dòng tiếp theo, chứa ~a_1~ và ~n~ , ~ (0 \leq a_1,n \leq 10^{15}) ~

có 50% test có ~ (0 \leq n \leq 10^{6}) ~

50% test còn lại không có điều kiện gì thêm

Output

~T~ dòng, mỗi dòng chứa 1 số nguyên duy nhất, số ~S~ được chia dư cho ~10^9 +7~.

có 50% test có ~ (0 \leq n \leq 10^{6}) ~

50% test còn lại không có điều kiện gì thêm

Sample Input

1
3 5

Sample Output

36