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?


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)


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


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

hide comments
kxbaphomet_666: 2021-06-17 13:19:02

@morass how can we be sure that a and b are non-negative?? and btw what is the reason for taking M so big instead of 1e9 + 7

zaid_25: 2020-12-10 09:41:13

why it is not accepting
pls help

:D: 2018-10-24 12:13:48

Time limit is per test file (there can be multiple). Results page shows the sum of execution times over all tests file. When program is being run you can sometimes see a description "running (A)" meaning test file number A is being tested at that moment.

Last edit: 2018-10-24 12:15:44
matusjuran: 2018-09-23 11:27:47

@morass If I may ask, why did my solutions get accepted despite the fact that all of them exceeded the 3s limit?

morass: 2017-08-26 16:52:18

@amit_ranjan: Well, there are "many" options for such input so you can choose any (for example any "a" and "b==0" shall be correct). Anyway it doesn't matter, since we don't have to find a/b for the answer.

Have nice day ^_^

amit_ranjan: 2017-08-26 15:59:27

@morass how can i find a and b for values like 0 0 0....

Last edit: 2017-08-26 15:59:50
morass: 2017-08-22 00:57:35

@KUNDAN KUMAR: Good day to you,

Guess you shall check on how to divide in "modular arithmetic" and how to multiply with big modulus ^_^

KUNDAN KUMAR: 2017-08-21 12:42:48

I am getting Wrong Answer. Can anyone help me about this?
PS: In Advance, Thanks

sanjay5797: 2017-07-04 15:47:36

I'm getting runtime error even passed the sample test cases......
can anyone help me out?

jayharsh: 2017-05-27 07:16:06

please tell me how do we get the test cases ?

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