11582 - Colossal Fibonacci Numbers!

第 i 個費氏數列元素被遞迴地定義如下：

• f(0) = 0 且f(1) = 1。
• f(i+2) = f(i+1) + f(i)，對於所有 i >= 0。

本題請你計算費氏數列的元素值。

輸入的第一列為整數 t (t <= 10,000)表示測試資料的組數，接下來每組測試資料包含三個整數 a, b, n，其中 0 <= a, b <= 2^64 (a 與 b 不同時為0)，且 1 <= n <= 1000。

請每組測試資料輸出 f(a^b)除以 n 的餘數。

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250

---

原文出處