Надихнувшись послідовністю чисел Фібоначчі, Халек вирішив, що він нічим не гірший за Леонарда і вирішив вигадати свою послідовність. Як відомо, завжди легше адаптувати щось старе, ніж придумати нове.

Послідовність Фібоначчі визначається так:

• ~a_1 = 1~
• ~a_2 = 1~
• ~a_{n} = a_{n - 2} + a_{n - 1}, n > 2~

Халек хоче замінити ~a_1~ і ~a_2~ і отримати нову послідовність - послідовність Халека. Але він ще не обрав ці значення. Тому для кожного ~x_i~, ~y_i~, ~n_i~ знайдіть n-те число в послідовності Халека, якщо ~a_1=x_i~, а ~a_2=y_i~. Оскільки число може бути занадто великим, то виведіть остачу від ділення на ~10^9 + 7~.

Input

В першому рядку дано одне ціле число t ~(1\le t \le 10^6)~.

Далі в кожному з t рядків дано 3 цілі числа ~x_i~, ~y_i~, ~n_i~ ~(1 \le x_i, y_i, n_i \le 10^6)~.

Output

Знайдіть для кожного запиту n-те число в послідовності Халека, якщо ~a_1=x_i~, а ~a_2=y_i~, і виведіть їх по модулю ~10^9 + 7~.

Sample Input 1

2
293 713 781
148 983 474

Sample Output 1

7399665
167666110

Sample Input 2

6
8 3 2
9 2 7
10 2 2
1 4 3
10 4 6
1 9 9

Sample Output 2

3
61
2
5
50
202