{"problem":{"name":"『STA - R3』高维立方体","description":{"content":"如下定义斐波那契数列： $$\\operatorname{fib}(n)=\\begin{cases}1&n\\le 2\\\\\\operatorname{fib}(n-1)+\\operatorname{fib}(n-2)&n>2\\end{cases}$$ 现在我们定义一个函数（注意在 $n<1$ 时这个函数的值是 $0$）： $$f(n)=\\sum_{i=1}^n\\operatorname{fib}^","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9510"},"statements":[{"statement_type":"Markdown","content":"如下定义斐波那契数列：\n$$\\operatorname{fib}(n)=\\begin{cases}1&n\\le 2\\\\\\operatorname{fib}(n-1)+\\operatorname{fib}(n-2)&n>2\\end{cases}$$\n\n现在我们定义一个函数（注意在 $n<1$ 时这个函数的值是 $0$）：\n\n$$f(n)=\\sum_{i=1}^n\\operatorname{fib}^2(i)$$\n\n由于求斐波那契数列的前缀和太简单了，你需要求出：\n$$\\sum_{i=1}^n\\operatorname{fib}(i)\\cdot(f(i-2)+\\operatorname{fib}^2(i)+\\operatorname{fib}(i))$$\n的值，答案对输入的 $p$ 取模。\n\n注：$\\operatorname{fib}^2(x)$ 表示 $\\operatorname{fib}(x)$ 的平方。\n\n## Input\n\n**本题有多组数据**。\n\n第一行一个整数 $T$，表示数据的组数。\n\n对于每组数据，一行两个整数 $n,p$。\n\n## Output\n\n对于每组数据，输出一行一个整数，表示答案对 $p$ 取模后的结果。\n\n[samples]\n\n## Note\n\n样例解释：\n\n对于第一组数据，$1\\times(0+1^2+1)+1\\times(0+1^2+1)=4$。\n\n对于第二组数据，$1\\times(0+1^2+1)+1\\times(0+1^2+1)+2\\times(1+2^2+2)=18$。  \n### 数据范围\n\n**本题采用捆绑测试。**\n\n- Subtask 1（5 points）：$n \\le 10^7$，$p=10^9+7$。\n- Subtask 2（20 points）：$T\\le 10^4$，$n \\le 10^8$，$p=10^9+7$。\n- Subtask 3（5 points）：$p=2$。\n- Subtask 4（15 points）：$p\\le 5$。\n- Subtask 5（30 points）：$T\\le 10^4$，$n \\le 10^8$。\n- Subtask 6（25 points）：无特殊限制。\n\n对于所有数据，$1\\le T\\le 2\\times 10^5$，$1\\le n\\le 10^{18}$，$2\\le p\\le 10^9+7$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9510","tags":["数学","O2优化","矩阵加速","Fibonacci 数列"],"sample_group":[["3\n2 100\n3 100\n4 100","4\n18\n60"]],"created_at":"2026-03-03 11:09:25"}}