NUMQDW  Number of quite different words
Let's consider the alphabet consisting of the first c roman uppercase letters, i.e. {A, B, C, D, E, F} if c is 6.
We will call two words quite different, if there is no common subsequence of length more than one between those two words. For example ABC and CBA are quite different, but ABBA and CADDCAD aren't, because AA is a subsequence of both words.
Given a word w you are to find the number of words of length n that are quite different from w.
Input
The first line will contain the number of test cases (at most 20). Then there will be pairs of lines, the first one containing the numbers n (n will fit into a 32bit signed integer and will be nonnegative) and c (1 <= c <= 6), the second one the word w. w will only consist of the first c letters of the roman alphabet and will have at most 10000 characters.
Output
Print one line for each test case, consisting only of the number of words that are quite different from w. As this number can be quite large, you just have to output its remainder when dividing by 4242.
Example
Input: 3 3 3 ABC 4 4 CADDCAD 100 3 A Output: 10 13 2223
hide comments
Rishav Goyal:
20151002 17:54:53
Ahh! finally learnt one new concept ! :) 

Scape:
20150723 16:31:04
Kudos, nice problem! 

Sourangsu :
20131213 14:37:41
Finally AC...after 3 WAs!! Nice Question... 

Buda IM (retired):
20110722 11:04:56
Beautiful problem ! Last edit: 20160921 11:24:09 
Added by:  overwise 
Date:  20050804 
Time limit:  2.712s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  selfinvented 