[Login|Register]
Problems

Status

Rank

Problem 1251
Song
Time Limit: 1000ms
Memory Limit: 65536kb
Description
"让我们荡起双桨   
小船儿推开波浪   
让我们荡起双桨
海面倒映着美丽的白塔   
四周环绕着绿树红墙   
小船儿轻轻
飘荡在水中   
迎面吹来了凉爽的风"
在小W的世界中,一首歌是以0..9组成的字符串。
小W的音乐老师是个非常漂亮的MM,所以小W从那时候起就喜欢上了唱歌。记忆中音乐老师总是很温柔,总是弹着手风琴,轻轻的笑着,小W当然喜欢上了音乐老师。为了让老师知道小W的心意,小W决定写一首数字之歌——长度为N的歌曲——送给老师。但是小W知道,同样喜欢音乐老师的小Z也要送给老师一首歌,长度为M。小W当然不想自己的歌中包含有小Z的歌,所以他用瞬间移动偷偷看了小Z的歌,现在小W想知道一共有多少种作曲方式可以保证自己的歌曲中不包含小Z的歌。因为方案很多,你需要输出方案数mod k。
Input
第一行为T(T<=10),表示有T个case.
每一个Case包括两行,第一行输入N,M,K.接下来一行输入M位数字,表示小Z的歌。
其中N<=10^9,M<=20,K<=1000
Output
小W想知道不包含小Z歌曲的作曲种数Ans,输出Ans模K取余的结果。
Sample Input
2
4 3 100 
111
2 1 100
0
Sample Output
81
81
Hint
第二组样例即求长度为2的不含0的方案数mod100,容易知道一共有{10..99}-{10,20,30,...,90}共81种
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).