题目描述

$n$ 个小球初始从左到右排成一排（编号 $1$ 到 $n$），你需要为每个球都涂上颜色（红色或者蓝色），使得任取一段长度为 $k$ 的连续小球区间，均满足以下所有条件：

• 该区间内至少有 $l_a$ 个红色球，至多有 $r_a$ 个红色球
• 该区间内至少有 $l_b$ 个蓝色球，至多有 $r_b$ 个蓝色球
• 该区间内不存在连续 $x$ 个小球颜色相同

求满足上述条件的涂色的方案数对 $998244353$ 取模后的结果。

两种涂色方案不同，当且仅当两种方案中至少有一个小球的颜色不同。

输入格式

一行包含七个整数 $n,k,l_a,r_a,l_b,r_b,x$，含义如上所述。

输出格式

输出一行一个整数，表示方案数对 $998244353$ 取模后的结果。

5 2 1 2 1 2 2

2

10 9 2 7 4 9 5

588

样例解释

无

数据规模与约定

下发文件

下发文件对应子任务 $3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 2 \times 10^5,1 \leq k \leq min(10,n),1 \leq l_a \leq r_a \leq k,1 \leq l_b \leq r_b \leq k, 1 \leq x \leq k$。