#P1393. Mivik 的标题

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

Mivik 的标题

题目背景

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

题目描述

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

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

输入格式

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

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

输出格式

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

3 2 2
1 1
623902721
6 3 4
1 2 3 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):无特殊限制。