#P1393. Mivik 的标题

    ID: 7781 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>字符串数学KMP 算法快速数论变换 NTT

Mivik 的标题

题目背景

Mivik 现在已经写好了他的书,他现在准备给这本书起个书名去投稿。

题目描述

由于 Mivik 写书是乱敲键盘敲出来的,他准备对书名干同样的事情。Mivik 的键盘上有 mm 个不同的按键,对应着 mm 个不同的字符。Mivik 决定在这个键盘上等概率随机敲 nn 次敲出标题。但出于某些原因,Mivik 希望书名中要包含有一个人的名字 SS。于是 Mivik 来问你,他随机敲出的标题有多大的概率包含有这个名字。

同样的,Mivik 并不喜欢奇形怪状的小数,所以你只需要输出这个概率对 998244353998244353 取模后的值。

输入格式

第一行三个整数 nnmmS|S|,其中 S|S| 代表这个名字的长度。

第二行给出 S|S| 个整数 aia_i,代表这个名字。

输出格式

一行一个整数,代表概率对 998244353998244353 取模后的值。

输入数据 1

3 2 2
1 1

输出数据 1

623902721

输入数据 2

6 3 4
1 2 3 2

输出数据 2

480636170

提示

样例解释

样例一:为方便描述,我们定义键盘上两个按键为 ab。那么长度为 3 的所有字符串共有 aaaaababaabbbaababbbabbb 这 8 个,其中包含有指定名字 aa 的共有 aaaaabbaa 这三个,则概率为 38\frac{3}{8},取模后得到 623902721。

数据范围

对于全部数据,有 1S1051\le |S|\le 10^5SnS+105|S|\le n\le |S|+10^51m1081\le m\le 10^8

Subtask 1 (5 pts):满足 m=1m=1

Subtask 2 (20 pts):满足 1n,m2501\le n, m\le 250

Subtask 3 (30 pts):满足 1n,m50001\le n, m\le 5000

Subtask 3 (45 pts):无特殊限制。