分数: 7 点
问题陈述
给你一个正整数序列 A = (A_1, A_2, \dots, A_N) 长度 N,和一个正整数 T.
有 \sum_{i=1}^N A_i 不同的位置。每个位置都涂上一个整数代表的颜色,并且正好有 A_i 涂有颜色的位置 i.
最初,您选择涂有颜色的位置之一 1,移动到该位置并标记它。然后,你完全重复以下操作 T 次:
- 选择与当前位置颜色不同的任何位置,然后移动到那里。
计算一下有多少种方式,毕竟 T 操作后,您将回到最初标记的位置。输出结果取模 998244353.
约束
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^{18}
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数
部分分数
该问题有部分评分:
- 如果您使用以下方法求解所有数据集 N \leq 3 \times 10^3,您将获得 5 点。
输入
输入由标准输入给出,格式如下:
N T A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 3 2 1 2
示例输出 1
4
让我们对位置进行如下标记:
- 最初标记的位置:位置 1
- 其他位置涂上颜色 1:位置 2
- 涂有颜色的位置 2:位置 3
- 两个位置涂上颜色 3:地点 4 和 5
那么,有 4 有效的移动顺序:
- 1 \to 3 \to 4 \to 1
- 1 \to 3 \to 5 \to 1
- 1 \to 4 \to 3 \to 1
- 1 \to 5 \to 3 \to 1
示例输入 2
10 31415926535897932 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045
示例输出 2
66487687