Migrated from Lutece 2738 啥b二次元 2

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上上回说到 Yo 和女朋友分手后全身心投入了二次元抽卡手游。 由于 Yo 和女朋友分手了所以现在有很多钱，Yo 氪了很多钱抽了很多卡。 Yo 总共拥有 $n$ 种卡牌，每种卡牌有一个战力值 $v_i$ 和花费 $c_i$ 。 Yo 将进行一次扫荡任务。 任务开始时 Yo 有 $m$ 点体力，Yo 可以进行若干次对战，每次对战消耗一点体力，每次对战可以选择若干张卡牌(或者不选卡牌)出战，每种卡牌都有无限张，每次出战每种卡牌都可以选无限次。这次扫荡的战果值为所有对战的所有出战卡牌战力的乘积，如果没有卡牌出战则为 $1$。 由于司马策划，任务开始时就需要确定对战次数，即选择一个非负整数 $k\in[0,m]$ 作为对战次数，那么 Yo 这 $k$ 次对战所选的所有卡牌花费之和需要不超过 $k$ 。 由于 Yo 和女朋友分手了所以现在有很多时间，所以 Yo 想知道所有不同情况的得到的战果值。 由于 Yo 还要玩二次元游戏，所以他只想知道所有可能情况的战果值之和对 $998244353$ 取模的结果。 由于 Yo 还要玩二次元游戏，所以他将这个问题交个你了。

两种情况不同当且仅当对战次数不同或者某次出战选择某种卡牌的次数不同。

Input

第一行输入两个整数 $n,m$ 表示卡牌种数和体力值。 第二行输入 $n$ 个空格隔开的整数 $c$ 表示每种卡牌的花费。 第三行输入 $n$ 个空格隔开的整数 $v$ 表示每种卡牌的战力。

Output

输出一个整数表示答案。

Samples

3 3
1 1 2
6 3 6

6559

7 6
1 2 4 3 2 4 5
15 7 13 12 11 14 4

339955269

Constraints

$1\le n,m\le 2\times10^5,0 < c\le m,0<v<998244353$

Note

样例1解释： 三种卡牌编号 $1,2,3$。

出战 $0$ 次：战果值为 $1$

出战 $1$ 次： 花费 $0$：战果值为 $1$ 花费 $1$： 出战 $1$ 号卡：战果值为 $6$ 出战 $2$ 号卡：战果值为 $3$ 和为 $10$

出战 $2$ 次： 花费 $0$：战果值为 $1$ 花费 $1$：选择一张 $1$ 号 $/$ $2$ 号，在第一 $/$ 二次出战四种情况：战果值和为 $18$ 花费 $2$：选择两张 $1$ 号 $/$ $2$ 号 两次都出战1号：$36$ 都出战 $2$ 号：$9$ 第一次 $1$ 号，第二次 $2$ 号：$18$ 第一次 $2$ 号，第二次 $1$ 号：$18$ 第一次出战两张 $1$ 号，第二次不出：$36$ 第一次出战两张 $2$ 号，第二次不出：$9$ 第一次出战一张 $1$ 号一张 $2$ 号，第二次不出：$18$ 第一次不出，第二次出战一张 $1$ 号一张 $2$ 号：$18$ 第一次不出，第二次出战两张 $1$ 号：$36$ 第一次不出，第二次出战两张 $2$ 号：$9$ 第一次出战一张 $3$ 号，第二次不出：$6$ 第一次不出，第二次出战一张 $3$ 号：$6$ 和为 $238$

出战 $3$ 次： 花费 $0$：战果值为 $1$ 花费 $1$：选择 $1$ 号 $/$ $2$ 号，在第一 $/$ 二 $/$ 三次出战六种情况：战果值和为 $27$ 花费 $2$： 选择一张 $3$ 号，三次出战中选一次：战果值为 $18$ 选择两张 $1$ 号 $/$ $2$ 号，分配在三次出战里： 两张 $1$ 号，战果值和为 $36*6=216$ 两张 $2$ 号，战果值和为 $9*6=54$ 各一张，战果值和为 $18*9=162$ 花费 $2$ 的战果值和为 $450$ 花费 $3$: 总共出战三张 $1$ 号卡，有 $10$ 种情况： 1/1/1 11//1 11/1/ 1/11/ /11/1 1//11 /1/11 111// /111/ //111 两个$/$隔开的即三次出战的卡牌编号 贡献为 $216\times 10=2160$ 三张 $2$ 号卡同理，贡献为 $27\times10=270$ 一张 $1$ 号卡两张 $2$ 号卡有 $18$ 种情况:$108\times18=1944$ 一张 $2$ 号卡两张 $1$ 号卡同理：$54\times18=972$ 一张 $1$ 号卡一张 $3$ 号卡有 $9$ 种情况：$36\times 9=324$ 一张 $2$ 号卡一张 $3$ 号卡同理：$18\times 9=162$ 花费 $3$ 的战果值和为 $5832$ 出战三次的战果值和为 $5832+1+27+450=6310$

则答案为 $1+10+238+6310=6559$

Resources

2022 UESTC ICPC Training for Math and Geometry