{"problem":{"name":"「DTOI-4」白的 Fibonacci","description":{"content":"定义 $F(k, n)$ 如下： $$ F(k,n) =  \\left \\{ \\begin{aligned} &st_0\\ && k = 1\\ \\land\\ n = 0 \\\\ &st_1\\ && k = 1\\ \\land\\ n = 1 \\\\ &0\\ && k > 1 \\ \\land \\ n < 0 \\\\ &a \\times F(k, n - 1) + b \\times F(k, n - 2)\\ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":65536},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8979"},"statements":[{"statement_type":"Markdown","content":"定义 $F(k, n)$ 如下：\n\n$$\nF(k,n) = \n\\left \\{\n\\begin{aligned}\n&st_0\\ && k = 1\\ \\land\\ n = 0 \\\\\n&st_1\\ && k = 1\\ \\land\\ n = 1 \\\\\n&0\\ && k > 1 \\ \\land \\ n < 0 \\\\\n&a \\times F(k, n - 1) + b \\times F(k, n - 2)\\ && k = 1 \\ \\land\\ n > 1 \\\\\n&t_k \\times F(k, n - 1) + s^n \\times F(k - 1, n)\\ && \\text{otherwise}\n\\end{aligned}\n\\right.\n$$\n\n给定 $F$ 递推式的各项系数和 $k, n$，请你求出 $F(k, n) \\bmod 998244353$ 的值。\n\n## Input\n\n第一行，两个整数 $k, n$；\n\n第二行，五个整数 $st_0, st_1, a, b, s$；\n\n第三行，$k - 1$ 个整数 $t_2, t_3, \\cdots, t_k$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n| $\\textbf{Subtask}$ | $k \\leq$ | $n \\leq$ | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $100$ | $100$ | 无 | $5$ |\n| $2$ | $100$ | $2^{63}$ | 无 | $25$ |\n| $3$ | $5000$ | $2^{63}$ | $s = 1, \\forall 2 \\leq i \\leq k, t_i = 1$ | $10$ |\n| $4$ | $5000$ | $2^{63}$ | 无 | $60$ |\n\n对于 $100\\%$ 的数据，$1 \\leq k \\leq 5 \\times 10^3$，$0 \\leq n \\le 2^{63}$，$-998244352 \\leq st_0, st_1, a, b, s, t_i \\leq 998244352$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8979","tags":["2023","多项式","洛谷原创","O2优化","线性递推"],"sample_group":[["10 25\n-5 -73 -95 64 15\n-80 -31 -58 15 95 -1 14 -30 31 ","998096342"]],"created_at":"2026-03-03 11:09:25"}}