TopCoder

Thumb fhvirus
FHVirus
$\Huge{破台後跑十圈操場 ZCK請 FIN }$

User's AC Ratio

94.6% (53/56)

Submission's AC Ratio

84.1% (74/88)

Description

給四個參數 $a, b, c, d$ 依照參數輸出答案

$Ans = a ^ c + (a+b) ^ c + (a+b+b) ^ c + (a+b+b+b) ^ c + \cdots + d ^ c$

保證 $(d - a) \mod b = 0$ 且 $d > a$。

Input Format

輸入四個正整數 $a, b, c, d \le 1000$。

Output Format

輸出答案。由於答案可能會很大,所以聰明的你一定會 $\mod 10 ^ 6$。

Sample Input

18 37 860 166

Sample Output

205154

Hints

Problem Source

原TIOJ1286 / 雄中公假社'08 入退社考。Problem Setter:ggm。
2021.03.11 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 (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5