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

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

\(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 Specification

В першому рядку дано одне ціле число 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 Specification

Знайдіть для кожного запиту 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