New TIOJ 新 TIOJ 已上線！舊 submission 已全數完成 rejudge，詳見公告。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
2053 . 費氏數列（Fibonacci）
TopCoder
Tags
Description
有一個數列，頭兩個數是0和1，接下來的每一個數$x_n$，都是兩個數的和，例如第三個數是$0 + 1 = 1$，第四個數是$1 + 1 = 2$，第五個數是$1 + 2 = 3$。我們知道這個數列是有名的費氏數列。
現在我們仿照費氏數列的生成方式來生成某個數列、該數列的頭兩個數是$x_1$和$x_2$，接下來的每一個數，都是$x_n = bx_{n - 1} + ax_{n - 2}$。給定$x_1, x_2, a, b$，請你寫一個程式計算指定的第$n$個數$x_n$。
Input Format
輸入只有一行，有五個正整數，依序為$x_1, x_2, a, b, n(0\leq x_1, x_2, a, b \leq 10^ 9, 3\leq n \leq 10^ 9$，數值間以空白隔開。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $x_1 = 0, x_2 = 1, a = b = 1, n\leq 30$ | 10 |
| 2 (5~12) | $x_1 = 0, x_2 = 1, a = b =1, n\leq 100$ | 10 |
| 3 (13~26) | $n \leq 1000$ | 10 |
| 4 (27~49) | 無 | 70 |
Output Format
由於$x_n$的數值可能很大，請輸出$x_n$除以$1000000007$的餘數。
Sample Input 1
0 1 1 1 5
Sample Output 1
3
Sample Input 2
0 1 1 1 50
Sample Output 2
778742000
Sample Input 3
3 4 5 6 999
Sample Output 3
434708377
Sample Input 4
999999999 999999999 999999999 999999999 999999999
Sample Output 4
302734374
Hints
Problem Source
2018 TOI入營考pC
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 10 |
| 2 | 5~12 | 10 |
| 3 | 13~26 | 10 |
| 4 | 27~49 | 70 |