No.2963 Mecha DESU
ねしん
遭難者ストーリー
惰弱な祭りに溺れる惰弱な正義ドンレンジャーを一喝すべく
今、ここに俺、来てれり
恐れを知らぬものならば、かかってこい！
(太鼓の達人ナムコオリジナル「メカデス。」より引用)
か〇ちゃん「しゅやくのざはわたさないドン！ボクのあついえんそうをきくドーン！！」
(太鼓の達人3DS 『ちびドラゴンと不思議なオーブ』より引用)
問題文
今、数直線上に $N$ 体のゾンビが存在し、$i=1,2,3,\cdots,N$ において座標 $i$ にゾンビが $1$ 体ずつ存在しています。
またカードが手札に $M$ 枚あり、$i$ 番目のカードに書かれている整数は $A_i$ です。
今から次の行動を $K$ 回繰り返します。
カードを選ぶ確率は等確率とし、行動ごとにカードを手札に戻すものとします。$K$ 回の操作の中で $1$ 回以上感電したゾンビの数の期待値を $\text{mod}$ $998244353$ で求めてください。
答えは分母が $998244353$ と互いに素の既約分数 $\frac{P}{Q}$ になるので、$Qx \equiv P$ $(\text{mod}$ $998244353)$ となる $x(0 \leq x \leq 998244352)$ を求めてください。
入力
$N$ $M$ $K$ $A_1$ $A_2$ $\cdots$ $A_M$
出力
感電しているゾンビの期待値を出力してください。
サンプル
サンプル1
入力
6 3 2 1 2 3
出力
110916044
引いたカードが
$(1,1)$ のときゾンビ $1,2,3,4,5,6$ が、
$(1,2)$ のときゾンビ $1,2,3,4,5,6$ が、
$(1,3)$ のときゾンビ $1,2,3,4,5,6$ が、
$(2,1)$ のときゾンビ $1,2,3,4,5,6$ が、
$(2,2)$ のときゾンビ $2,4,6$ が、
$(2,3)$ のときゾンビ $2,3,4,6$ が、
$(3,1)$ のときゾンビ $1,2,3,4,5,6$ が、
$(3,2)$ のときゾンビ $2,3,4,6$ が、
$(3,3)$ のときゾンビ $3,6$ が、
感電しています。よって感電しているゾンビの数の期待値は $\frac{43}{9}$ 体です。
サンプル2
入力
5 1 1 6
出力
0
$1$ 体も感電しないこともあります。
サンプル3
入力
49 7 5 1 3 5 7 7 9 21
出力
375551832
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。