#P17744. 超级加倍

超级加倍

题目描述

在欢乐斗地主中,一共有n 种加倍卡,其中每一种都能使倍数变成原来的wiw_{i}倍。特别的,在此我们认为底倍数为1。

当然,仅仅一次加倍是不能满足人们心中的快感的,所以腾讯推出了新的加倍方式——「超级加倍」。

定义一次「超级加倍」为进行m 次加倍操作,其中每次加倍操作可以在n 种加倍卡中任意选择一张卡进行加倍。特别的,在「超级加倍」中,每一种加倍卡的出现次数不限。

作为策划师的你,为了判断「超级加倍」的强度,你需要回答所有本质不同的「超级加倍」的倍数的和。当然,由于欢乐豆是有限的,你只需要回答对998244353 取模后的结果。

「超级加倍」A、B 本质不同定义为:存在至少一个i,使得第i

种加倍卡在A 中的出现次数不等于在B 中的出现次数。

例如,如果m=2,n=2,2 种加倍卡倍率分别为w1w_{1}和w2w_{2},则共有4

种情况:

1.第一次选w1w_{1},第二次选w2w_{2},总倍率为w1w2w_1w_2.

2.第一次选w2w_{2},第二次选w1w_{1},总倍率为w1w2w_1w_2.

3.第一次选w1w_{1},第二次选w1w_{1},总倍率为w1w1w_1w_1.

4.第一次选w2w_{2},第二次选w2w_{2},总倍率为w2w2w_2w_2.

在第一种和第二种方案中,都获取了一张w1w_{1}和一张w2w_{2},所以我们认为它们是本质相同的,所以上面例子中共有三种本质不同的方案,

权值和为(w1w2+w1w1+w2w2)(w_1w_2+w_1w_1+w_2w_2)。

注意,即便存在i、j 的加倍倍数一样,i、j 仍视作本质不同的两种加倍卡;比如在上一个例子中,如果w1w_{1}=w2w_{2},本质不同的超级加倍的方案仍然有三种,而不是一种。

输入格式

从标准输入读入。

第一行两个数,分别为n、m。

第二行n 个数,第i 个表示wiw_{i}。

输出格式

输出到标准输出。

一行一个整数,表示所有本质不同的「超级加倍」的倍数的和。

输入样例

2 3
2 3

输出样例

65

样例解释

一共有四种本质不同的超级加倍:

选择0 张第1 种卡,3 张第2 种卡,此时倍数为3∗3∗3=273*3*3=27;

选择1 张第1 种卡,2 张第2 种卡,此时倍数为2∗3∗3=182*3*3=18;

选择2 张第1 种卡,1 张第2 种卡,此时倍数为2∗2∗3=122*2*3=12;

选择3 张第1 种卡,0 张第2 种卡,此时倍数为2∗2∗2=82*2*2=8;

所以倍数和为65

数据约定

对于10%的数据,有n,m≤7。

对于30%的数据,有n,m≤100。

对于50%的数据,有n≤5,m≤10510^{5}。

对于70%的数据,有n≤200,m≤10510^{5}。

对于100%的数据,有n≤200,m≤10910^{9},0<=wiw_{i}<998244353