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 32-bit signed integer and will be non-negative) 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

Added by:overwise
Date:2005-08-04
Time limit:2.712s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:self-invented

hide comments
2015-10-02 17:54:53 Rishav Goyal
Ahh! finally learnt one new concept ! :-)
2015-07-23 16:31:04 Scape
Kudos, nice problem!
2013-12-13 14:37:41 Sourangsu
Finally AC...after 3 WAs!! Nice Question...
2011-07-22 11:04:56 Buda IM (retired)
Beautiful problem !

Last edit: 2016-09-21 11:24:09
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.