Total Submission(s): 126 Accepted Submission(s): 11

Problem Description

As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)^{2} +A(1)^{2}+¡¡+A(n)^{2}.

Input

There are several test cases.

Each test case will contain three integers , N, X , Y .

N : 2<= N <= 2^{31} ¨C 1

X : 2<= X <= 2^{31}¨C 1

Y : 2<= Y <= 2^{31} ¨C 1

Each test case will contain three integers , N, X , Y .

N : 2<= N <= 2

X : 2<= X <= 2

Y : 2<= Y <= 2

Output

For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.

Sample Input

2 1 1 3 2 3

Sample Output

6 196

Author

wyb