配点 : 100 点
問題文
1,2,\ldots ,N 有 N 行李件左右并排放置。一、行李 它被放置在第 i 从左起 代表 i 个位置。此外,每件行李都有规定的重量,并且 i 的权重是 A_i 。
您对此包列执行以下一系列操作。 0 您可以随意执行多次。 小于或等于
- 1 \le L \lt R \le N 的一组整数 (L,R) 从左起 第 L,L+1, \ldots ,R 件行李的总重量为 K 类似的东西 循环将第 1 选择一项。
- 从左起 从第 L,L+1, \ldots ,R 个包向左移动。也就是说,从左边开始 放置在 L 位置的行李是从左边开始的。 从左侧开始,使其处于第 R 位置。 放置在 L+1,\ldots ,R 位置的行李是从左边开始的。 移动行李,使其位于第 L,\ldots ,R-1 位置。
计算所有操作完成后包裹可能的排列方式的数量。 998244353 后求余数。
制約
- 所有输入均为整数
- 2 \le N \le 2 \times 10^5
- 1 \le K \le 10^{14}
- 1 \le A_i \le 10^8
入力
输入按以下格式给出。
N K A_1 A_2 \ldots A_N
出力
打印答案。 来自
入力例 1
4 7 1 2 2 3
出力例 1
12
初始状态下,从左起 第 2,3,4 件行李的总重量为 2+2+3=7 \ge K=7 所以作为第一个操作 您可以选择 (L,R)=(2,4) 。执行此操作后,包裹编号将从左到右编号。 1,3,4,2 。 对于
所有操作完成后整理行李的可能方式 12 如下。
请注意,即使包裹的重量相同,包裹也会根据数量进行区分。在这种情况下,包裹编号是从左到右依次排列的。 1,2,3,4 排列1,3,2,4 被视为不同的排列。
入力例 2
2 100 1 1
出力例 2
1
操作是 1 您甚至可能无法执行此操作一次。 请回答除以
入力例 3
20 1 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
出力例 3
401576539
998244353 后的余数。