TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

95.3% (41/43)

Submission's AC Ratio

60.0% (54/90)

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

Sample Input #1
0 1 1 1 5

Sample Input #2
0 1 1 1 50

Sample Input #3
3 4 5 6 999

Sample Input #4
999999999 999999999 999999999 999999999 999999999

Sample Output

Sample Output #1
3

Sample Output #2
778742000

Sample Output #3
434708377

Sample Output #4
302734374

Hints

Problem Source

2018 TOI入營考pC

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 5 ~ 12, Score: 10
For Testdata: 13 ~ 26, Score: 10
For Testdata: 27 ~ 49, Score: 70
No. Time Limit (ms) Memory Limit (KiB)
0 1000 262144
1 1000 262144
2 1000 262144
3 1000 262144
4 1000 262144
5 1000 262144
6 1000 262144
7 1000 262144
8 1000 262144
9 1000 262144
10 1000 262144
11 1000 262144
12 1000 262144
13 1000 262144
14 1000 262144
15 1000 262144
16 1000 262144
17 1000 262144
18 1000 262144
19 1000 262144
20 1000 262144
21 1000 262144
22 1000 262144
23 1000 262144
24 1000 262144
25 1000 262144
26 1000 262144
27 1000 262144
28 1000 262144
29 1000 262144
30 1000 262144
31 1000 262144
32 1000 262144
33 1000 262144
34 1000 262144
35 1000 262144
36 1000 262144
37 1000 262144
38 1000 262144
39 1000 262144
40 1000 262144
41 1000 262144
42 1000 262144
43 1000 262144
44 1000 262144
45 1000 262144
46 1000 262144
47 1000 262144
48 1000 262144
49 1000 262144