Description

When Xiao Keke visited the science museum, she saw an exhibit covered with dense numbers, as shown below:

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

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?

Input Format

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

Output Format

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

1 2 99

2

9 1 999

22

Hint

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

Translated by ChatGPT 5