版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/P12668

题目描述

给你一棵高度为 $k+2$ 的树，从底往上，树的第 $0$ 层（即最底层）有 $n+m$ 个点，其中有 $n$ 个点是黑色的，$m$ 个点是白色的。树的第 $i\in[1,k]$ 层有 $a_i$ 个节点，这些点没有颜色。树的根节点连向每个第 $k$ 层的节点。

你需要构造一种连边方案，满足除最底层节点外，每个节点至少有一个儿子节点。并且使得从树的根节点出发，每次随机地走到该节点的一个儿子节点，一直走到最底层节点为止，停留在黑色节点的概率最大。你需要输出最大概率对 $998244353$ 取模的结果。

输入格式

由于数据过大无法上传，所以你需要用一种特殊方式读入 $a_i$。

第一行 $3$ 个整数 $n,m,k$。

第二行 $3$ 个整数 $a_1,d,x$，表示 $a_1$ 的值以及两个参数，剩下的 $a$ 可以通过以下计算得到：

特别的，当 $k=0$ 时，你应该忽略掉第二行的内容。

注释：$a \oplus b$ 代表 $a$ 和 $b$ 的按位异或值。

输出格式

一行 $1$ 个整数，表示你能够被宽恕的最大概率对 $998244353$ 取模的结果。

样例

1 2 1
2 0 0

499122177

3 4 3
6 1 1

831870295

样例 1 解释

一共只有 $1$ 种盒子，该种盒子有 $2$ 个。
先把 $1$ 颗黑子放入一个盒子中，再把 $2$ 颗白子放入另一个盒子中即可达到最大概率。
答案为 $\frac{1}{2}$，取模后为 $499122177$。

样例 2 解释

一共只有 $3$ 种盒子，每种盒子分别有 $6$ 个，$4$ 个，$2$ 个。
答案为 $\frac{5}{6}$，取模后为 $831870295$。

数据范围

对于全部的数据：$0\le n,m\le 10^9$，$0\le x\le d\le 10^9$，$0\le k\le 10^7$，$1\le a_k\le a_{k-1}\le\dots\le a_1\le n+m\le2\times10^9$，详细数据范围见下表。

数据保证答案在模 $998244353$ 下有意义。

注：默认内存限制是 $512$ MB。