#P1393. Mivik 的标题
Mivik 的标题
题目背景
Mivik 现在已经写好了他的书,他现在准备给这本书起个书名去投稿。
题目描述
由于 Mivik 写书是乱敲键盘敲出来的,他准备对书名干同样的事情。Mivik 的键盘上有 个不同的按键,对应着 个不同的字符。Mivik 决定在这个键盘上等概率随机敲 次敲出标题。但出于某些原因,Mivik 希望书名中要包含有一个人的名字 。于是 Mivik 来问你,他随机敲出的标题有多大的概率包含有这个名字。
同样的,Mivik 并不喜欢奇形怪状的小数,所以你只需要输出这个概率对 取模后的值。
输入格式
第一行三个整数 、、,其中 代表这个名字的长度。
第二行给出 个整数 ,代表这个名字。
输出格式
一行一个整数,代表概率对 取模后的值。
3 2 2
1 1
623902721
6 3 4
1 2 3 2
480636170
提示
样例解释
样例一:为方便描述,我们定义键盘上两个按键为 a
和 b
。那么长度为 3 的所有字符串共有 aaa
、aab
、aba
、abb
、baa
、bab
、bba
、bbb
这 8 个,其中包含有指定名字 aa
的共有 aaa
、aab
、baa
这三个,则概率为 ,取模后得到 623902721。
数据范围
对于全部数据,有 ,,。
Subtask 1 (5 pts):满足 。
Subtask 2 (20 pts):满足 。
Subtask 3 (30 pts):满足 。
Subtask 3 (45 pts):无特殊限制。