{"problem":{"name":"The Lost Symbol","description":{"content":"设二元运算符 $k\\operatorname A n$ 为排列数 ${\\rm A}_n^k$，$k \\operatorname C n$ 为组合数 ${\\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。 给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\\textrm A,\\textrm C$ 的序列 ${\\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8946"},"statements":[{"statement_type":"Markdown","content":"设二元运算符 $k\\operatorname A n$ 为排列数 ${\\rm A}_n^k$，$k \\operatorname C n$ 为组合数 ${\\rm C}_n^k$，定义 $k>n$ 时两者的值都为 $0$。\n\n给定 $n,m$ 和一个长度为 $n-1$ 的仅包含 $\\textrm A,\\textrm C$ 的序列 ${\\rm opt}_{[1,n-1]}$，对所有长度为 $n$，且每一个数都是 $[1,m]$ 中的整数的序列 $a_{[1,n]}$ 求 $(\\cdots(((a_1\\operatorname{opt}_1 a_2)\\operatorname{opt}_2 a_3)\\operatorname{opt}_3 a_4)\\cdots\\operatorname{opt}_{n-2}a_{n-1})\\operatorname{opt}_{n-1}a_n$ 的和。\n\n答案对质数 $11417603$ 取模。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n接下来一行一个长度为 $n-1$ 的字符串表示 $\\text{opt}$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/g4ofcg40.png)\n\n## Note\n\n#### 【样例解释】\n对于样例 #1：\n\n$1\\operatorname C 1=1$，$1\\operatorname C 2=2$，$2\\operatorname C 1=0$，$2\\operatorname C 2=1$，求和为 $4$。\n\n对于样例 #2：\n\n$1\\operatorname A 1=1$，$1\\operatorname A 2=2$，$2\\operatorname A 1=0$，$2\\operatorname A 2=2$，求和为 $5$。\n\n#### 【数据范围】\n\n不开启捆绑测试，按点给分。\n\n对于 $100\\%$ 的数据，$2\\leq n,m\\leq 10^5$，${\\rm opt}$ 仅包含 $\\textrm A,\\textrm C$。\n\n| 测试点编号 | $n\\leq$ | $m\\leq$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1\\sim3$ | $8$ | $8$ | 无 | \n| $4\\sim6$ | $314$ | $159$ | 无 | \n| $7\\sim10$ | $2718$ | $2818$ | 无 | \n| $11\\sim13$ | $10^5$ | $10^5$ | $\\rm opt$ 仅由 $\\rm A$ 构成 |\n| $14\\sim16$ | $10^5$ | $10^5$ | $\\rm opt$ 仅由 $\\rm C$ 构成 |\n| $17\\sim20$ | $10^5$ | $10^5$ | $\\rm opt$ 由不超过 $10$ 段连续的 $\\rm A$ 和连续的 $\\rm C$ 拼接而成 |\n| $21,22$ | $8492$ | $10^5$ | 无 |\n| $23\\sim25$ | $10^5$ | $10^5$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8946","tags":["2023","洛谷原创","O2优化"],"sample_group":[["2 2\nC","4"],["2 2\nA","5"],["8 8\nCCACAAC","399968"]],"created_at":"2026-03-03 11:09:25"}}