To read the problem statement in English, choose the language using the flag on the navigation bar.

Lộc thích màu lam đậm, nên lần đầu tiên mà Lộc đăng kí tài khoản trên một trang Online Judge giấu tên, Lộc đã quyết định sử dụng nickname darkcyan. Buồn thay, nickname này đã được sử dụng. Vì nickname bị trùng lặp, hệ thống có gợi ý Lộc sử dụng các nickname khác như darkcyan_no1, darkcyan_pro và darkcyan_vip, tuy nhiên Lộc không thích các nickname đó. Sau một hồi đắn đo suy nghĩ, nickname mà Lộc chọn là darkkcyan, rất gần với nickname ban đầu, nhưng kí tự k được nhân đôi lên. Và thật may mắn là nickname này chưa tồn tại! Nickname này đã được Lộc sử dụng cho hệ thống này cũng như trên nhiều nền tảng khác nhau.

Lộc nhận thấy rằng việc thay đổi nickname như thế thật là thú vị, và có thể áp dụng ý tưởng này để tạo ra một hệ thống gợi ý nickname hoàn toàn mới! Cụ thể, với một nickname được biểu diễn bởi xâu gồm ~k~ kí tự ~t_1 t_2 \ldots t_l~, hệ thống có thể biến đổi nickname sử dụng theo tác sau một số lần (có thể là 0 lần):

• Hệ thống chọn ra một vị trí ~i~ (~1 \le i \le l~) ngẫu nhiên. Các vị trí đều có xác suất được chọn là như nhau. Hệ thống sau đó sẽ chèn ~c~ kí tự ~t_i~ vào ngay sau vị trí ~i~. Các kí tự mới có chỉ số là ~i + 1, i + 2, \ldots, i + c - 1~ và các kí tự sau đó có chỉ số được tăng lên ~c~. Độ dài của nickname mới sẽ là ~l + c~.

Số lượng ~c~ các kí tự sẽ chèn thêm sẽ được hệ thống tính toán như sau:

1. Gán ~c \leftarrow 1~.

2. Hệ thống sẽ liên tục tung một đồng xu có xác suất sấp ngửa là 50/50. Trong khi đồng xu còn ngửa, hệ thống sẽ tăng ~c~ lên một.

3. Bước thứ hai có thể được lặp lại bởi hệ thống nhiều lần, tuy nhiên nếu ~c~ đã đạt đến giới hạn ~k~, hệ thống sẽ dừng tính toán giá trị ~c~ tại đây.

Cụ thể hơn, số ~c~ sẽ được tính toán bởi mã giả sau:

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

Ví dụ, với nickname darkcyan (với độ dài là ~8~) và giới hạn ~k = 3~.

• Nickname darkkcyan sẽ có xác suất được tạo ra là ~\frac{1}{8} \cdot 50\% = \frac{1}{16}~ (xác suất chọn kí tự k là ~\frac{1}{8}~ và xác suất cho việc tung đồng xu ra mặt sấp là ~50\%~). Các nickname khác như ddarkcyan, darrkcyan hay darkcyann cũng có xác suất được tạo ra tương tự.

• Nickname darkkkcyan sẽ có xác suất được tạo ra là ~\frac{1}{8} \cdot 50\% \cdot 50\% = \frac{1}{32}~ (xác suất chọn kí tự k là ~\frac{1}{8}~ và xác suất cho việc tung đồng xu ra đầu tiên ra mặt ngửa là ~50\%~, và xác suất để tung đồng xu thứ hai ra mặt sấp là ~50\%~). Các nickname khác như dddarkcyan, darrrkcyan hay darkcyannn cũng có xác suất được tạo ra tương tự.

• Các nickname darkkkkcyan, ddddarkkcyan, darrrrkcyan hay darkcyannnn sẽ có xác suất được tạo ra không phải là ~\frac{1}{64}~, mà cũng là ~\frac{1}{32}~, do lúc này số lượng kí tự ~c~ được thêm vào đã đạt đến ~k = 3~.

Lưu ý: với ~k = -1~, ta có thể coi số lần tung đồng xu là không giới hạn.

Thiết kế của hệ thống này có sử dụng phương pháp ngẫu nhiên để sinh ra nickname mới. Lộc quyết định thiết kế như vậy để giảm thiểu chi phí cho việc kiểm tra nickname tồn tại trong quá trình tạo ra nickname mới, nhưng khả năng tạo ra một nickname ngắn gọn vẫn rất cao với số bước cần thực hiện được kì vọng là không quá lớn.

Lộc nghĩ rằng sẽ thật đáng tiếc nếu như không có hệ thống gợi ý nickname trùng lặp nào sử dụng ý tưởng này. Do đó Lộc quyết định áp dụng luôn hệ thống gợi ý nickname này cho mạng xã hội Virtual Network for Online Intercommunication (VNOI) mà mình đang tham gia phát triển. Hiện tại trên mạng xã hội VNOI đã có ~n~ người dùng, và người dùng thứ ~i~ có nickname là xâu kí tự ~S_i~. Lộc muốn biết rằng, với mỗi nickname ~S_i~, nếu nếu như có một người dùng mới khi đăng kí hệ thống sử dụng nickname trùng với nickname này, vậy giá trị kì vọng số thao tác thao tác biến đổi nickname này để tạo ra một nickname chưa được sử dụng trên VNOI là bao nhiêu. Vì Lộc vẫn đang bận phát triển thành phần khác của hệ thống, nên Lộc muốn nhờ các bạn giải quyết bài toán này.

Cho danh sách nickname của ~n~ người dùng trên hệ thống, yêu cầu với mỗi nickname ~S_i~, cần in ra giá trị kì vọng số thao tác biến đổi để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống. Để đảm bảo các kết quả được so sánh một cách chính xác, hãy in ra đáp án modulo ~10^9 + 7~.

Cụ thể hơn, đặt ~M = 10^9 + 7~. Ta có thể chỉ ra rằng đáp án có thể biểu diễn bởi một phân số tối giản ~\frac{p}{q}~, với ~p~ và ~q~ nguyên tố cùng nhau và ~q \not \equiv 0 \pmod{M}~. Hãy in ra số nguyên ~p \cdot q^{-1} \bmod M~. Nói cách khác, hãy in ra số nguyên ~x~ thỏa mãn ~0 \le x < M~ và ~x \cdot q \equiv p \pmod{M}~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^5~, ~1 \le k \le 10^9~ hoặc ~k = -1~) là số lượng người dùng mạng xã hội VNOI và giới hạn số kí tự có thể được thêm vào trong 1 phép biến đổi. Nếu ~k = -1~, số lượng kí tự được thêm vào là không giới hạn.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa xâu ~S_i~ (~1 \le |S_i| \le 10^5~, ~S_i~ chỉ chứa các kí tự tiếng Anh in thường) là nickname của người dùng thứ ~i~ trên hệ thống.

Dữ liệu đảm bảo tổng độ dài của tất cả các nickname trên hệ thống không quá ~10^5~ và không tồn tại hai nickname nào giống nhau.

Output

In ra ~n~ dòng. Dòng thứ ~i~ là giá trị kì vọng số lượng thao tác biến đổi để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống, modulo ~10^9 + 7~.

Scoring

• Subtask 1, tương ứng với ~45~ điểm, có ~1 \le k \le 10~.

• Subtask 2, tương ứng với ~105~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~150~ điểm.

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

Trong ví dụ đầu tiên, nickname aa cần kì vọng ~\frac{3}{2}~ thao tác biến đổi. Do hai kí tự giống nhau, nên ta có thể bỏ qua đi xác suất chọn kí tự trong xâu và tính toán dựa vào xác suất tung đồng xu:

• Xác suất cho việc tạo ra xâu aaa là ~50\%~ nếu như trong lần đầu tiên tung đồng xu ra kết quả sấp. Vì nickname này đã trùng nên ta cần thêm 1 lần biến đổi nữa. Không quan trọng kết quả cuối cùng, trong trường hợp này ta cần ~2~ thao tác biến đổi.

• Xác suất cho việc tạo ra xâu aaaa là ~50\%~ do giới hạn số lượng kí tự có thể thêm vào là ~k = 2~. Vì không có nickname nào khác trùng với nickname này, nên ta cần ~1~ thao tác biến đổi.

Do đó kì vọng số lượng biến đổi sẽ là ~50\% \cdot (2 + 1) = \frac{3}{2}~.

Nickname a trong ví dụ đầu tiên cần kì vọng ~\frac{9}{4}~ thao tác biến đổi.

Trong ví dụ thứ hai không có giới hạn số lượng kí tự có thể thêm vào. Nickname b khi đó có khả năng biến đổi sau:

• tạo ra nickname bbb với xác suất ~50\% \cdot 50\% = 25\%~. Trong trường hợp này, không kể kết quả cuối cùng, ta cần thêm một thao tác biến đổi nữa vì đây là nickname đã tồn tại, do đó trường hợp này ta cần ~2~ thao tác biến đổi.

• tạo ra nickname khác bbb với xác suất là ~1 - 25\% = 75\%~. Trong trường hợp này ta thu được một nickname mới, do đó ta cần ~1~ thao tác biến đổi.

Do đó kì vọng số lượng biến đổi sẽ là ~25\% \cdot 2 + 75\% \cdot 1 = \frac{5}{4}~ thao tác biến đổi.