{"problem":{"name":"[LMXOI Round 1] Random","description":{"content":"给出一个初始全为 $0$ 长为 $n$ 的序列，我们会进行如下操作 $q$ 次。 + 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。 也就是说我们一共会有 $(nk)^q$ 种不同的询问序列，而对于每一种不同的询问序列，对应的也就拥有了 $(nk)^q$ 个结果序列。 接着，给出一个长度为 $m$ 匹配序列 $B$，需要求出这个匹配序列在每一个结果序列","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10116"},"statements":[{"statement_type":"Markdown","content":"给出一个初始全为 $0$ 长为 $n$ 的序列，我们会进行如下操作 $q$ 次。\n\n+ 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。\n\n也就是说我们一共会有 $(nk)^q$ 种不同的询问序列，而对于每一种不同的询问序列，对应的也就拥有了 $(nk)^q$ 个结果序列。\n\n接着，给出一个长度为 $m$ 匹配序列 $B$，需要求出这个匹配序列在每一个结果序列中出现的次数和。注意，一个结果序列中若出现多个匹配序列应当重复计算。\n\n由于答案太大，你只需要输出答案对 $998244353$ 取模后的结果。\n\n**本题使用特定方式生成输入数据。**\n\n生成格式如下： $x_i=(a \\times i+b)\\bmod k +1$ ，其中 $x_i$ 表示序列 $B$ 第 $i$ 位所需求的数字。\n\n## Input\n\n第一行四个整数 $n,m,q,k$ 其中 $m$ 为 $B$ 序列的长度。\n\n第二行二个整数 $a,b$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Background\n\nLMX 给 HQZ 一个有趣的序列，HQZ 为了了解 LMX 的爱好，想要解决下面的问题。  \n\n## Note\n\n**样例解释 #1**\n\n下述操作序列，存在序列 $B$：\n+ $[1,1],[2,2]$ 序列为 $[1,2,0]$\n+ $[2,2],[1,1]$ 序列为 $[1,2,0]$\n+ $[2,1],[3,2]$ 序列为 $[0,1,2]$\n+ $[3,2],[2,1]$ 序列为 $[0,1,2]$\n\n对于 $100\\%$ 的数据，保证 $\\forall x_i \\in B, 1\\le x_i\\le k$，$0 \\le a,b\\le 10^9$，且 $m\\le n$。\n\n| 子任务编号 |      $n,q,k$      |    $m$    | 特殊性质 |  分值  |\n| :--------: | :------------------: | :----------: | :------: | :----: |\n| Subtask #1 |     $\\le 10^9$     | $\\le 200$ | $q< m$ | $5$ |\n| Subtask #2 |      $\\le 4$      |  $\\le 4$  |    无    | $10$ |\n| Subtask #3 |     $\\le 500$     | $\\le 200$ |    无    | $10$ |\n| Subtask #4 | $\\le 2\\times 10^5$ | $\\le 200$ |    无    | $20$ |\n| Subtask #5 |     $\\le 10^9$     | $\\le 200$ |    无    | $20$ |\n| Subtask #6 |     $\\le 10^9$     | $\\le 3\\times 10^6$ |    无    |   $35$   |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10116","tags":["O2优化","组合数学","容斥原理"],"sample_group":[["3 2 2 2\n1 1","4"],["2 1 2 2\n1 1","12"],["10 3 114 51419\n19 2","266405589"]],"created_at":"2026-03-03 11:09:25"}}