Migrated from Lutece 1568 Aston1shed Poker

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The evil invented poker, and poker made people depraving.

As you known, a deck of poker consists of $52$ cards, each card has a suit and a rank.

There are four suits in a deck of poker, we use the characters in set $\\{s, h, d, c\\}$ representing the suits spades $\spadesuit$, hearts $\heartsuit$, diamonds $\diamondsuit$, and clubs $\clubsuit$.

The rank of a card is represented as an integer from $1$ to $13$.

Now you are given $N$ pairwise distinct cards from a deck of poker, you need to calculate the ways to arrange these cards such that there are no $K$ successive card(s) which have the same rank.

Input

There are two integers $N$ and $K$ in the first line.

For the next $N$ lines, each line describes a card, represented by it's rank and suit, see the sample for more details.

$1 \leq N \leq 52$, $1 \leq K \leq 5$.

Output

Print the number of ways to arrange these cards modulo $10^9 + 7$.

Samples

3 2
12h
13h
13s

2

Resources

The 15th UESTC Programming Contest Final