题目描述

小可可参观科学博物馆时看到一件藏品，上面有密密麻麻的数字，如下所示：

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  …

仔细一分析，发现还挺有规律。原来，第一行是斐波那契（Fibonacci）数列。即，该行中除了第一个和第二个数分别为1和2之外，其他数都是其左侧相邻的两个数之和。其后各行也类似于Fibonacci数列。只是第$i$行的第一个数是前$i$-1行中未出现的最小正整数，而其第二个数与该行第一个数以及所在行的编号相关，即$A[i,2]=2A[i,1]-(i-1)$。如在第一行中未出现的最小正整数为4，前三行中未出现的最小正整数为9。故第二行以4和7开头，而第四行以9和15开头。

小可可高兴地把这个发现告诉了爷爷。爷爷问道：你能否一口报出第$i$行、第$j$列的那个数对$m$取模的结果是多少呢？

聪明的小可可通过心算就能知道答案。你是否能编写程序求解呢？

输入格式

输入每行有三个分别用一个空格隔开的正整数，分别是$i、j$和$m$。

输出格式

每行输出对应的第i行、第j列的那个正整数对m取模的结果。

样例

1 2 99
9 1 999

2
22

数据范围

$i,j≤10^9,2≤m≤10^4$

来源

• 信息学奥赛之数学一本通
• stong9070整理