1912 : yifan and string

Our brother yifan has some problems about strings, one of them is following.
Given an string S and an integer n, we called the string S is Devil's string, now you need to calculate how many Lucky string which length is n. We regard an string is lucky if it doesn't contain S as substrings

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 letters that you can use to  create lucky strings. This non-empty line contains lowercase characters only and in ascending order. The third line contains the Devil's 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.

1
5
ab
aaa

Case 1: 24