Ada the Ladybug's crush Bumblebee Blazewan has a secret diary. Ada wants to read it to see, whether he loves her too. Sadly, the diary is locked with some very strong cipher so she can't read it.

She asked you for help. Unfortunately, you are not able to break through. Yet you observed, that the key generated in the cipher is generated in following way X_i+1=(aX_i+b) mod (10¹¹+3). You was able to find out first six X_i's. Predicting next will help you to get through - can you do it?

Input

There will be no more than 10⁵ test-cases.

Each test-case consists of line containing 6 integers 0 ≤ X_i < 10¹¹+3 (1 ≤ i ≤ 6)

Output

For each test-case print X₇ (modulo 100000000003).

Example Input

2 10 34 106 322 970
2 4 4 4 4 4
2 11 47 191 767 3071
0 0 0 0 0 0
2 8 32 128 512 2048

Example Output

2914
4
12287
0
8192

Possible setting

a=3, b=4, X1=2
a=0, b=4, X1=2
a=4, b=3, X1=2
a=2, b=0, X1=0
a=4, b=0, X1=2