Arc of Dream

Time Limit: 2000/2000 MS (Java/Others)

Memory Limit: 65535/65535 K (Java/Others)

Description

An Arc of Dream is a curve defined by following function:

where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

Input

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

Output

For each test case, output AoD(N) modulo 1,000,000,007.

Sample Input

1 1 2 3 4 5 6 2 1 2 3 4 5 6 3 1 2 3 4 5 6

Sample Output

4 134 1902

Hint

zhuyuanchen520

Source

2013 Multi-University Training Contest 9

提交代码