UOJ Logo Universal Online Judge

UOJ

#694. 【UR #23】国王出游

附件下载 统计

跳蚤国王兴致大发,在刚建好的跳蚤利亚上游玩!

跳蚤利亚的布局是网格状,因为它太大了,我们把它看成一个坐标系,其中 $(0,0)$ 是跳蚤国王的城堡,y 轴正方向是正北,x 轴正方向是正东。

跳蚤国王初始在 $(x_0,y_0)$ 视察工作,每一秒,假设跳蚤国王在 $(x,y)$,就会等概率随机走到 $(x+A,y),(x-B,y),(x,y+C),(x,y-D)$ 中的一个位置。

跳蚤国王计划走 $T$ 秒,如果最终他走到了 $(x_T,y_T)$,那么这次出游,他的愉悦度就是 $x_T^ny_T^m$,即 $x_T$ 的 $n$ 次方乘以 $y_T$ 的 $m$ 次方。

国王想知道,他这次出游愉悦度的期望对 $998244353$ 取模后的结果。

输入格式

一行九个整数 $n,m,T,x_0,y_0,A,B,C,D$,含义见上。

输出格式

一行一个整数,表示期望对 $998244353$ 取模后的结果。可以证明答案一定可以被表示为 $\frac{a}{b}$ 的形式,其中 $\gcd(a,b)=1$,你需要输出整数 $c$ 满足 $bc\equiv a\bmod 998244353$。

样例一

input

2 3 2 0 1 1 1 2 3

output

748683270

explanation

一共有 $16$ 种可能。

$~$ $(1,0)$ $(-1,0)$ $(0,2)$ $(0,-3)$
$(1,0)$ $(2,1):4$ $(0,1):0$ $(1,3):27$ $(1,-2):-8$
$(-1,0)$ $(0,1):0$ $(-2,1):4$ $(-1,3):27$ $(-1,-2):-8$
$(0,2)$ $(1,3):27$ $(-1,3):27$ $(0,5):0$ $(0,0):0$
$(0,-3)$ $(1,-2):-8$ $(-1,-2):-8$ $(0,0):0$ $(0,-5):0$

愉悦度的期望为:$\frac{84}{16}=\frac{21}{4}$,而 $4\times 748683270\equiv 21\pmod 998244353$。

样例二、三、四

见附件下载。

数据范围与提示

子任务编号 $n,m\leq$ $T\leq$ 特殊性质 分值
$1$ $2000$ $2000$ $20$
$2$ $100000$ $10^9$ $1$ $20$
$3$ $100000$ $2,3$ $10$
$4$ $10^9$ $2,3$ $10$
$5$ $2$ $10$
$6$ $3$ $20$
$7$ $10$

特殊性质 $1$:$A=B=C=D=1$。

特殊性质 $2$:$A\neq B,C\neq D$。

特殊性质 $3$:$x_0=y_0=0$。

对于所有数据,$0\leq n,m\leq 10^5,0\leq T\leq 10^9,0\leq x_0,y_0,A,B,C,D\lt 998244353$。

时间限制:$\texttt{5s}$

空间限制:$\texttt{512MB}$