TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

93.8% (45/48)

Submission's AC Ratio

24.9% (87/350)

Tags

Description

如果說一個數列 $s$ 符合:

  • $s_0 = a$
  • $s_1 = b$
  • $s_b = x \cdot a_{n-2} + y \cdot a_{n-1} \ \ \forall n \geq 2$

那我們就稱這個數列為索拉數列(sola sequence)。
索拉數列有一些有趣的特性,不過那不在我們的討論範圍。

風祭雅最近才剛學到索拉數列,老師便出了一大堆題目要她算讓她覺得很煩,
於是就要求身為勞工的你幫她寫個程式計算一個給定參數的索拉數列某一項的值,
請趕快把這個程式寫出來,不然她又要扣你薪水了 @@"

Input Format

輸入有多行,每行有五個非負整數分別是:$n, a, b, x, y$。
其中,$n \leq 10 ^ 9$
而 $a, b, x, y < 2 ^ {32}$。
當 $n$ 是負數時則代表輸入結束。

Output Format

對於輸入資料的每一行印出一個數字代表答案。
由於這個數字可能很大,只要輸出除以 $2 ^ {32}$ 之後的餘數就可以了。

Sample Input 1

0 0 1 1 1
1 0 1 1 1
2 0 1 1 1
3 0 1 1 1
4 0 1 1 1
5 0 1 1 1
2 5 7 2 1
-1

Sample Output 1

0
1
1
2
3
5
17

Hints

Problem Source

原TIOJ1331 / Problem Setter:akira

2021.02.14 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 2
2 500 65536 262144 3
3 500 65536 262144 4
4 500 65536 262144 5