题目描述

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

$\red{1 ~~ 2 ~~ 3 ~~5 ~~ 8 ~~ 13 ~~ 21 ~~34 ~~55 ~~ 89 ~~ 144 ...}$

$\red{4 ~~ 7 ~~ 11 ~~18 ~~ 29 ~~ 47 ~~ 76 ~~123 ~~199 ~~ 322 ~~ 521 ...}$

$\red{6 ~~ 10~~ 16 ~~26 ~~ 42 ~~ 68 ~~ 110 ~~178 ~~288 ~~ 466 ~~ 754 ...}$

$\red{9 ~~ 15~~ 24 ~~39 ~~ 63 ~~ 102~~ 165 ~~267 ~~432 ~~ 699 ~~ 1131 ...}$

$\red{12~~ 20~~ 32 ~~52 ~~ 84 ~~ 136~~ 220 ~~356 ~~576 ~~ 932 ~~ 1508...}$

$\red{14~~ 23~~ 37 ~~60 ~~ 97 ~~ 157~~ 254 ~~411 ~~665 ~~ 1076~~ 1741 ...}$

$\red{17~~ 28~~ 45 ~~73 ~~ 118~~ 191~~ 309 ~~500 ~~809 ~~ 1309~~ 2118 ...}$

$\red{19~~ 31~~ 50 ~~81 ~~ 131~~ 212~~ 343 ~~555 ~~898 ~~ 1453~~ 2351 ...}$

$\red{22~~ 36~~ 58 ~~94 ~~ 152~~ 246~~ 398 ~~644 ~~1042~~ 1686~~ 2728 ...}$

$\red{25~~ 41~~ 66 ~~107~~ 173~~ 280~~ 453 ~~733 ~~1186~~ 1919~~ 3105 ...}$

$\red{27~~ 44~~ 71 ~~115~~ 186~~ 301~~ 487 ~~788 ~~1275~~ 2063~~ 3338 ...}$

$\red{...}$

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

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

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

输入格式

输人每行有三个分别用一个空格隔开的正整数,分别是$\red{i}$、$\red{j}$和$\red{m}$。其中,$\red{i，}$$\red{j≤}$$\red{10^9，}$ $\red{2≤}$$\red{m≤}$$\red{10^4}$。

输出格式

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

样例

输入样例1

1 2 99

输出样例1

2

输入样例2

9 1 999

输出样例2

22