巨大的斐波那契数！ Colossal Fibonacci Numbers!

题意翻译

输入两个非负整数 $a, b$ 和正整数 $n(0 \le a, b < 2^{64}，1 \le n \le 10^3)$ ，求 $f(a ^ b) \bmod n$ 的值, 其中 $f_0 = 0, f_1 = 1, f_{i + 2} = f_i + f_{i + 1}(i\ge 0)$。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2629 [PDF](https://uva.onlinejudge.org/external/115/p11582.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11582/793174b7cb7a81b759e4bbca17e8b25bd80837d1.png)

输入输出格式

输入格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11582/a692210c8dc9ff34408062fbfbbcc6071357e2bb.png)

输出格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11582/09aad5c02f463a372c8c69399918c9b2c20e65c7.png)

输入输出样例

输入样例 #1

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

输出样例 #1

1
21
250