Lộc likes dark cyan, because of that, when Lộc registers his first
account on a mysterious Online Judge, he chose the nickname `darkcyan`

.
Unfortunately, this nickname was taken. The system recommends Lộc a
couple of other nicknames, some of which are `darkcyan_no1`

,
`darkcyan_pro`

and `darkcyan_vip`

, none of which Lộc liked at all. After
spending a few eternities pondering, the nickname chosen by Lộc was
`dar`

, very similar to the initial nickname, only duplication the
__kk__cyan`k`

. This nickname turns out wasn't taken! So it became Lộc's new
nickname for many other different Online Judges.

Lộc finds changing nicknames like this interesting, and he applies this idea to create an entirely novel nickname suggestion system! For a nickname that's represented by a string with ~k~ characters ~t_1 t_2 \ldots t_l~, the system can change the nickname using the following operation several (possibly zero) times:

- The system selects an integer ~i~ (~1 \le i \le l~)
**at random**. Each position has equal probability of being chosen. The system then inserts ~c~ occurrences of the character ~t_i~ right after position ~i~. The new character's indices are ~i + 1, i + 2, \ldots, i + c - 1~ and the indices of every following characters are increased by ~c~. The length of the new nickname will be ~l + c~.

The exact value of ~c~, the number of extra characters inserted, is calculated as follow:

Initially, ~c \leftarrow 1~.

The system tosses a fair coin, having 50/50 chance of landing on either sides. While the coin lands on heads, ~c~ is increased by one.

The previous step may be repeated many times. However if ~c~ has already reached the limit ~k~, the system stops at that value of ~c~.

Formally, the value ~c~ is calculated with the following pseudocode

```
c = 1;
while c != k and coinToss() == head:
c = c + 1;
```

For example, suppose the starting nickname is `darkcyan`

(with length
~8~) and the limit ~k = 3~.

Nickname

`dar`

has a creation probability of ~\frac{1}{8} \cdot 50\% = \frac{1}{16}~ (the probability of choosing the character__kk__cyan`k`

is ~\frac{1}{8}~ and the probability of the coin toss landing*tails*is ~50\%~). Some other nicknames such as

,__dd__arkcyan`da`

or__rr__kcyan`darkcya`

has equal probability of being created to this one.__nn__Nickname

`dar`

has a creation probability of ~\frac{1}{8} \cdot 50\% \cdot 50\% = \frac{1}{32}~ (the probability of choosing the character__kkk__cyan`k`

is ~\frac{1}{8}~ and the probability of the first coin toss landing*heads*~50\%~, the probability of the second coin toss landing*tails*~50\%~). Some other nicknames such as

,__ddd__arkcyan`da`

or__rrr__kcyan`darkcya`

has equal probability of being created to this one.__nnn__Nicknames

`dar`

,__kkkk__cyan

,__dddd__arkkcyan`da`

or__rrrr__kcyan`darkcya`

has a probability of creation__nnnn__**not**~\frac{1}{64}~, but also ~\frac{1}{32}~, because at this point, ~c~ has already reached the ~k = 3~ limit.

**Note:** For ~k = -1~, the number of possible coin tosses is **not
limited**.

This design uses randomization to generate new nicknames. Lộc decides to go for this design choice to reduce cost of checking nickname availability, yet the probability of generating a brand new unused nickname is very high without needing to expect too many steps in the generating process.

Lộc thinks it's a pity if there's no existing nickname recommendation
system like this. So he decides to implement this system for the social
network *Virtual Network for Online Intercommunication* (VNOI) that he's
developing. On VNOI there are currently ~n~ users, the ~i~-th of which
has the nickname ~S_i~. Lộc wants to know, for each nickname ~S_i~, if
there is a new user who attempts to register with this nickname, what is
the **expected** number of steps needed to transform this username into
a brand new, unused username, following the aforementioned procedure. As
Lộc is a very busy developing other parts of the system, he needs your
help to solve this problem.

Given the list of nicknames of the ~n~ users on the system, for each
nickname ~S_i~, calculate the **expected** number of operations to turn
~S_i~ into a new, unused nickname, on the system. To ensure your
calculations are correct, output the answer modulo ~10^9 + 7~.

Formally, let ~M = 10^9 + 7~. We can show that the answer can be represented as an irreducible fraction ~\frac{p}{q}~, where ~p~ and ~q~ are integers and ~q \not \equiv 0 \pmod{M}~. Output ~p \cdot q^{-1} \bmod M~. In other words, output such an integer ~x~ that ~0 \le x < M~ and ~x \cdot q \equiv p \pmod{M}~.

#### Input

The first line contains two integers ~n~ and ~k~ (~1 \le n \le 10^5~,
~1 \le k \le 10^9~ or ~k = -1~), denoting the number of VNOI users and
the character limit in one operation. If ~k = -1~, the number of
characters that may be added in one operation is **not limited**.

The ~i~-th out of the next ~n~ lines each contain a single string ~S_i~ (~1 \le |S_i| \le 10^5~, ~S_i~ consists only of lowercase latin letters) denoting the nickname of the ~i~-th user.

Is it guaranteed that the total length of all nicknames do not exceed ~10^5~, and no two nicknames are the same.

#### Output

Output ~n~ lines. The ~i~-th line should contain the *expected number*
of operations needed to transform nickname ~S_i~ into a nickname that
has not appeared in the system, modulo ~10^9 + 7~.

#### Scoring

Subtask 1 (~45~ points): ~1 \le k \le 10~.

Subtask 2 (~105~ points): no additional constraints.

The total score for this problem is ~150~.

#### Sample Input 1

```
3 2
aaa
aa
a
```

#### Sample Output 1

```
1
500000005
250000004
```

#### Sample Input 2

```
2 -1
b
bbb
```

#### Sample Output 2

```
250000003
1
```

#### Sample Input 3

```
3 1
ab
aab
abb
```

#### Sample Output 3

```
2
1
1
```

#### Notes

In the first sample, the nickname `aa`

is expected to take ~\frac{3}{2}~
operations. Since the two operations are the same, we can skip the
character selection, and only look at the coin tossing process:

The probability of the result string being

`aaa`

would be ~50\%~ for getting tails on the first coin toss. Since this nickname has already appeared, we need another operation. Regardless of how the second operation turns out, we get a new nickname, thus the number of operations is ~2~.The probability of the result string being

`aaaa`

is ~50\%~ for the character addition limit is ~k = 2~. Since there is no other nickname matching this, we need ~1~ operation in this case.

Therefore the expected number of operations is ~50\% \cdot (2 + 1) = \frac{3}{2}~.

For the nickname `a`

in the first sample, the expected number of
operations is ~\frac{9}{4}~.

In the second sample, the number of characters that can be added in one
operation is unlimited. The nickname `b`

thus has the following
outcomes:

Creating the nickname

`bbb`

with probability ~50\% \cdot 50\% = 25\%~. In this case, we need one more operation to create a new nickname, thus the number of operations needed is ~2~.Creating the nickname

**other than**`bbb`

with probability ~1 - 25\% = 75\%~. In this case we have already obtained a new nickname, thus ~1~ is the number of operations needed.

Therefore, the expected number of operations is ~25\% \cdot 2 + 75\% \cdot 1 = \frac{5}{4}~.

## Comments