P2544 [AHOI2004] Number Maze

When Xiao Keke visited the science museum, she saw an exhibit covered with dense numbers, as shown below: ```text 1 2 3 5 8 13 21 34 55 89 144 … 4 7 11 18 29 47 76 123 199 322 521 … 6 10 16 26 42 68 110 178 288 466 754 … 9 15 24 39 63 102 165 267 432 699 1131 … 12 20 32 52 84 136 220 356 576 932 1508 … 14 23 37 60 97 157 254 411 665 1076 1741 … 17 28 45 73 118 191 309 500 809 1309 2118 … 19 31 50 81 131 212 343 555 898 1453 2351 … 22 36 58 94 152 246 398 644 1042 1686 2728 … 25 41 66 107 173 280 453 733 1186 1919 3105 … 27 44 71 115 186 301 487 788 1275 2063 3338 … … ``` After some analysis, she found a clear pattern. It turns out that the first row is the Fibonacci sequence. That is, in this row, except for the first and second numbers which are 1 and 2 respectively, every other number is the sum of the two numbers immediately to its left. The subsequent rows are also similar to the Fibonacci sequence. The first number of row $i$ is the smallest positive integer that has not appeared in the previous $i - 1$ rows, and the second number of that row is related to the first number and the row index $i$, namely $$ A[i,2] = 2A[i,1] - (i - 1). $$ For example, the smallest positive integer not appearing in the first row is 4, and the smallest positive integer not appearing in the first three rows is 9. Therefore, the second row begins with 4 and 7, and the fourth row begins with 9 and 15. Xiao Keke happily told her grandfather about this discovery. Grandpa asked: Can you immediately tell, for the number at row $i$ and column $j$, what its value modulo $m$ is? Clever Xiao Keke can figure it out mentally. Can you write a program to compute it?

A single line containing three positive integers $i, j, m$.

Output a single line with one positive integer: the value of the number at row $i$ and column $j$ modulo $m$.

Constraints: For all testdata, $i, j \le 10^9$, $2 \le m \le 10^4$. Translated by ChatGPT 5