Time Limit: 2 second(s) | Memory Limit: 32 MB |
Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.
One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.
So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 10^{9}). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.
For each case, print the case number and the total number of names that don't contain S as substring. As the number can be very large, print the number modulo 2^{32}.
Sample Input |
Output for Sample Input |
3 3 ab ab 4 acd ca 5 ab aaa |
Case 1: 4 Case 2: 55 Case 3: 24 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |