快速幂
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
Special for beginners, ^_^
Description
：快速幂就是快速算底数的 次幂。其时间复杂度为 ， 与朴素的 相比效率有了极大的提高。快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
例如(暗色模式看不清)：
相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法等运算也遵循矩阵的运算法则。对于矩阵的基本运算这里不再做赘述。
： (或 )，表示 除以 的余数。
现在给你一个递推公式：
求该数列的第 项。由于答案可能过大，你只需要输出答案对 取模后的值。
Format
Input
一个正整数 () 。
Output
一个整数，对应答案。
Samples
1
2
2
3
如果没有解题思路，可以算一下前几项看看。
Limitation
1s, 1024KiB for each test case.
