Alisa rất thích chơi piano bằng một ngón tay. Xui xẻo thay, Alisa chưa bao giờ học chơi piano, nên cách chơi của cô ấy là hoàn toàn ngẫu nhiên. Chính xác hơn, mỗi lần Alisa chọn một nốt nhạc để chơi, cô sẽ chọn một trong ~N~ nốt với xác suất như nhau và độc lập với các nốt đã chơi trước đó.

Bạn tốt của cô, Mirta muốn nghe một bản nhạc gồm ~M~ nốt nhạc liên tiếp nhau. Nhưng do Alisa chơi piano một cách ngẫu nhiên, Mirta không biết cô sẽ phải chờ bao lâu để được nghe hết bản nhạc này. Mirta là một cô gái rất tò mò nên cô muốn biết, với mỗi tiền tố của bản nhạc, giá trị kì vọng số nốt Alisa sẽ đánh để được nghe liên tiếp các nốt trong tiền tố đó lần đầu tiên. Hãy giúp Mirta xác định các giá trị này.

Input

Dòng đầu tiên chứa một số nguyên dương ~N~, là số lượng nốt nhạc khác nhau có trên đàn piano ~(1 \le N \le 100)~.

Dòng thứ hai chứa một số nguyên dương ~M~, là độ dài bản nhạc mà Mirta muốn nghe ~(1 \le M \le 10^6)~.

Dòng thứ ba chứ ~M~ số nguyên dương trong khoảng từ ~1~ tới ~N~.

Output

In ra ~M~ dòng, dòng thứ ~i~ chứa một số nguyên dương là giá trị kì vọng số nốt Alisa sẽ chơi để Mirta nghe được tiền tố độ dài ~i~ của bản nhạc đã cho, chia lấy số dư cho ~10^9 + 7~.

Dữ liệu đầu vào đảm bảo các giá trị này sẽ luôn là số nguyên.

Sample 1

Input

2
2
1 2

Output

2
4

Sample 2

Input

2
2
1 1

Output

2
6

Sample 3

Input

3
3
1 2 3

Output

3
9
27

Ràng buộc

• ~10~ test đầu tiên thỏa mãn ~1 \le M \le 200~.
• ~10~ test còn lại không có thêm ràng buộc gì.