ADAHACK - Ada and Diary

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 Xi+1=(aXi+b) mod (1011+3). You was able to find out first six Xi's. Predicting next will help you to get through - can you do it?

Input

There will be no more than 105 test-cases.

Each test-case consists of line containing 6 integers 0 ≤ Xi < 1011+3 (1 ≤ i ≤ 6)

Output

For each test-case print X7 (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

Added by:Morass
Date:2017-02-10
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-05-27 00:08:09
@jai1998: Hello, depends on language you are using. For example in C/C++, you can use "while(~scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f))" / "while(cin>>a>>b>>c>>d>>e>>f)"

GL & Have Nice Day
2017-05-26 17:42:38
How to get number of test cases ?
2017-02-13 14:41:27
@gomathi ganesan: As you know 'a' and 'b', you can generate next "element" as Xi+1=(aXi+b) mod (10^11+3). That means if you would know 'a' and 'b', then this problem would be just about "putting it to expression" [i.e. very trivial].

That means with knowledge of a,b,X1, you can generate all (any) next elements.

Good Luck & Have nice day!
2017-02-13 08:37:14 gomathi ganesan
Can you explain the role of 'a' and 'b' through the example test cases?
2017-02-10 12:56:23 abdou_93
Why TLE!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.