题目描述

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

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$ 行中未出现的最小正整数，而其第二个数与该行第一个数以及所在行的编号 $i$ 相关，即

如在第一行中未出现的最小正整数为 4，前三行中未出现的最小正整数为 9。故第二行以 4 和 7 开头，而第四行以 9 和 15 开头。

小可可高兴地把这个发现告诉了爷爷。爷爷问道：你能否一口报出第 $i$ 行、第 $j$ 列的那个数对 $m$ 取模的结果是多少呢？
聪明的小可可通过心算就能知道答案。你是否能编写程序求解呢？

输入格式

输入一行三个正整数 $i,j,m$。

输出格式

输出一行一个正整数，表示对应的第 $i$ 行，第 $j$ 列的那个正整数对 $m$ 取模的结果。

1 2 99

2

9 1 999

22

提示

对于所有数据，$i,j\le10^9,2\le m\le10^4$。