2942. [AHOI 2004] 数字迷阵

【题目描述】

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

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_{i2} = 2A_{i1}-(i-1)$。如在第一行中未出现的最小正整数为 $4$，前三行中未出现的最小正整数为 $9$。故第二行以 $4$ 和 $7$ 开头，而第四行以 $9$ 和 $15$ 开头。

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

【输入格式】

一行，包含三个正整数，分别是$i,j,m$。

【输出格式】

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

【样例输入1】

1 2 99

【样例输出1】

2

【样例输入2】

9 1 999

【样例输出2】

22

【样例输入3】

999999 9999 9999

【样例输出3】

3431

【数据规模与约定】

对于 $10\%$ 的数据，$1 \leq i,j \leq 3000$;

对于 $30\%$ 的数据，$1 \leq i,j \leq 10^6$;

对于 $100\%$ 的数据，$1 \leq i,j \leq 10^9,2 \leq m \leq 10^4$;