2584: 例1.6-2 数字迷阵
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小可可参观科学博物馆时看到一件藏品，上面有密密麻麻的数字，如下所示：
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$取模的结果是多少呢？
聪明的小可可通过心算就能知道答案。你是否能编写程序求解呢？
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$
$i,j≤10^9,2≤m≤10^4$