## WOWSUBSTR2 - Counting WOW-Substrings2

You are given a string. You have to count the total lengths of allWOWsubstrings.WOWsubstrings are defined as a contiguous substring of a string

where there is no any character occurring more than one times.

That means, all the characters of substring are unique.

As answer could be very large, so print it modulo100007. (NOTE THAT: 100007 is not a prime number!!)

### Input

Input starts with an integer **TC**(<=50), denoting the number of test cases.

Each case starts with N and M, denoting respectively length of string and

total characters of string represented as integers from 1 to M. Then,follows

a line with space separated N integers ( each in the range 1 to M ).

Input starts with an integer TC(<=50), denoting the number of test cases.Each case starts with a string S.

All characters in string will consists of only lowercase letters of English alphabets.

### Output

For each case, print the case number and total lengths of all WOW substrings of given string modulo **100007**.

**Constraints:**

**1<=TC<=50.**

**1<=N<=500000. (Length of string)**

**1<=M<=1000000.(Character id range)**

### Example

Input:

23 2

1 2 1

4 3

2 1 3 2Output:Case1: 7Case 2: 16

Added by: | BISHAL GAUTAM |

Date: | 2016-11-21 |

Time limit: | 0.200s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 GOSU |

Resource: | MySelf |