An Arc of Dream is a curve defined by following function:
where
a
0 = A0
a
i = a
i-1*AX+AY
b
0 = B0
b
i = b
i-1*BX+BY
What is the value of AoD(N) modulo 1,000,000,007?
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 10
18, and all the other integers are no more than 2×10
9.
For each test case, output AoD(N) modulo 1,000,000,007.