题目背景

SudoXue 又不知道这道题能配什么图片，于是放了一只猫猫。

帮助完噜噜，SudoXue 又迷上了数学，但他不会期望，于是求助于你。

题目描述

设质数

$$p = 998\,244\,353$$

所有除法均在模 $p$ 意义下进行。 记数列 $g(i,j)$ 满足

• 第 0 行：$g(0,j)=0\;(j\ge0)$。
• 第 $i\ge1$ 行 第 0 列：

$$g(i,0)=\sum_{t=0}^{2i}[t\text{ 为偶数}]\cdot t.$$

• 第 $i\ge2$ 行 第 $1\le j\le i-1$ 列：

$$\begin{aligned} g(i,j)=\;&\frac{g(i-1,j-1)}{ij} +\frac{\,g(i-1,j-1)+[j<i-1]\,g(i-1,j)}{i}\\[4pt] &+\frac{g(i-1,j-1)}{j} +g(i-1,j-1) +[j\ne i-1]\,g(i-1,j). \end{aligned} $$

• 循环节：第 $i$ 行仅保留 $g(i,0),\dots,g(i,i-1)$ 共 $i$ 项，并按此循环无限延展。

给定

• 正整数 $k=2^{t}\;(1\le t\le21)$；

• 实参 $x\in[0,10^{18}]$；

• 随机二次多项式

  $$Q(x)=a x^{2}+b x+c, \quad a\in[1,n],\;b\in[1,m],\;c\in[1,l], $$

  其中 $a,b,c$ 独立且均匀分布。

设

$$q \equiv Q(x)\pmod{k},$$

求随机变量 $g(k,q)$ 的 数学期望，并输出其在模 $p$ 下的值。

输入格式

一行五个整数 $n,m,l,k,x$。

输出格式

一行一个整数：所求期望值在模 $p$ 下的结果。

2 2 1 2 1

6

数据规模与约定

子任务	分数占比	参数范围	额外条件
1	$20\%$	$1 \le n,m,l \le 200$ $k = 2^{t},\;1 \le t \le 12\;$ $0 \le x \le 10^{18}$	—
2	$30\%$	$1 \le n,m,l \le 1000$ $k = 2^{t},\;5 \le t \le 15\;$ $0 \le x \le 10^{18}$	保证 $x$ 能被 $k$ 整除
3	$50\%$	$1 \le n,m,l \le 10^{12}$ $k = 2^{t},\;17 \le t \le 21\;$ $0 \le x \le 10^{18}$	—

对于 $100\%$ 的数据，保证$n \bmod p \ne 0,\quad m \bmod p \ne 0,\quad l \bmod p \ne 0$。