{"problem":{"name":"黑暗（Darkness）","description":{"content":"铃在一个黑暗的三维空间内寻找澪。这个空间可以表示为 $\\{(x,y,z) \\mid x \\in[0,A],y \\in [0,B],z\\in [0,C] \\}$。铃初始站在坐标为 $(A,B,C)$ 处，澪站在 $(0,0,0)$ 处。假设铃在 $(x,y,z)$ 处，她每次移动会**均匀随机**地尝试移动到 $(x-1,y,z)$ 或 $(x,y-1,z)$ 或 $(x,y,z-1)$。 这个空","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8558"},"statements":[{"statement_type":"Markdown","content":"铃在一个黑暗的三维空间内寻找澪。这个空间可以表示为 $\\{(x,y,z) \\mid x \\in[0,A],y \\in [0,B],z\\in [0,C] \\}$。铃初始站在坐标为 $(A,B,C)$ 处，澪站在 $(0,0,0)$ 处。假设铃在 $(x,y,z)$ 处，她每次移动会**均匀随机**地尝试移动到 $(x-1,y,z)$ 或 $(x,y-1,z)$ 或 $(x,y,z-1)$。\n\n这个空间的外围是墙壁，不可穿过。由于空间内很暗，铃并不知道自己是否走到了墙边。也就是说，她在随机选择三种方向尝试移动时，有可能撞在墙上。\n\n铃想要知道，自己在第一次撞墙时，「到澪的曼哈顿距离（在本题中的情况就是 $x,y,z$ 坐标之和）」的 $k$ 次方的期望值。\n\n你只需要求出答案对 $998244353$ 取模的结果。\n\n## Input\n\n输入一行四个正整数 $A,B,C,k$。\n\n## Output\n\n输出一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n【样例 $1$ 解释】 \n\n下表列出了走到各处并撞到墙的概率：\n\n| $(0,0,0)$ | $(1,0,0)$ | $(0,1,0)$ | $(0,0,1)$ | $(1,1,0)$ | $(1,0,1)$ | $(0,1,1)$ |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n| $2/9$ | $4/27$ | $4/27$ | $4/27$ | $1/9$ | $1/9$ | $1/9$ |\n\n可以发现只有在这 $7$ 个位置有可能撞到墙。由此算出期望值为 $\\dfrac{10}{9}$，在模 $998244353$ 意义下为 $443664158$。\n\n【样例 $2,3$ 解释】   \n\n这里要算的都是距离的平方的期望。实际答案分别为 $\\dfrac{30083}{2187}$ 和 $\\dfrac{22748643655}{387420489}$。\n\n【数据范围】  \n\n**本题采用捆绑测试。**\n\nSubtask1（8 pts）：$1\\le A,B,C,k\\le 6$；   \nSubtask2（19 pts）：$1\\le A,B,C \\le 100$；  \nSubtask3（13 pts）：$k=1$；  \nSubtask4（23 pts）：$1\\le A,B,C,k \\le 10^5$；  \nSubtask5（37 pts）：无特殊限制。\n\n对于 $100\\%$ 的数据，$1\\le A,B,C \\le 5\\times 10^6$，$1\\le k \\le 10^7$。\n\n【提示】  \n\n对于离散随机变量 $X$，其取值等于 $k$ 的概率设为 $P_k$，则 $X$ 的期望值定义为：\n\n$$\\sum_k kP_k$$\n\n对于有理数 $a/b$（$a,b$ 均为正整数），若整数 $r$ 满足 $r\\in[0,p-1]$ 且 $rb \\equiv a \\pmod p$，则 $r$ 就是 $a/b$ 对 $p$ 取模的结果。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8558","tags":["数学","洛谷原创","O2优化","组合数学","期望"],"sample_group":[["1 1 1 1","443664158"],["2 3 4 2","128260948"],["4 6 9 2","622775535"],["58 88 133 233","128518400"],["114514 1919810 4999231 8214898","823989766"]],"created_at":"2026-03-03 11:09:25"}}