| [Home|Training|Problems|Contests|C Language] | [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种
|