Advanced nickname suggestion system

View as PDF

Submit solution

Points: 1.20 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 darkkcyan, very similar to the initial nickname, only duplication the 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:

  1. Initially, ~c \leftarrow 1~.

  2. 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.

  3. 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 darkkcyan has a creation probability of ~\frac{1}{8} \cdot 50\% = \frac{1}{16}~ (the probability of choosing the character k is ~\frac{1}{8}~ and the probability of the coin toss landing tails is ~50\%~). Some other nicknames such as ddarkcyan, darrkcyan or darkcyann has equal probability of being created to this one.

  • Nickname darkkkcyan has a creation probability of ~\frac{1}{8} \cdot 50\% \cdot 50\% = \frac{1}{32}~ (the probability of choosing the character 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 dddarkcyan, darrrkcyan or darkcyannn has equal probability of being created to this one.

  • Nicknames darkkkkcyan, ddddarkkcyan, darrrrkcyan or darkcyannnn has a probability of creation 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

Please read the guidelines before commenting.


There are no comments at the moment.