Lala năm nay mới vào lớp một. Sáng nay, Lala được học về phép tính cộng. Khi về nhà, Lala đã hứng thú đến nỗi đòi anh trai ~-~ Alex cho mình thêm các bài tập về phép cộng.

Alex của rất vui khi thấy được niềm đam mê toán học của em gái mình. Alex viết ra ~N~ con số vào một tờ giấy. Và đánh dấu các con số theo thứ tự ~1 \rightarrow N~ (kí hiệu ~a_{i}~ là số thứ ~i)~. Bây giờ Lala được cho thêm số ~S~ và phải viết ra tất cả các bộ số {~p_{1}~, ~p_{2}~, ~p_{3}~, ..., ~p_{x}~}, sao cho ~p_{1} < p_{2} < \dots < p_{x}~ và ~a_{p_{1}} + a_{p_{2}} + \dots + a_{p_{x}} = S~. Sau khi nghe xong câu hỏi, Lala liền hỏi ngược lại Alex: "Nếu vậy thì với mỗi số ~1~, ~2~, ~3~, ..., ~(N - 2)~, ~(N - 1)~, ~N~, Lala phải viết ít nhất bao nhiêu lần để làm xong bài tập trên vậy anh?!! ".

Lala thì đã cặm cụi viết ra các bộ số từ lâu. Còn Alex thì đang nhức óc với câu hỏi trên. Các bạn hãy giúp Alex giải nhanh câu đố trên trước khi Lala làm xong bài tập nhé. Nếu không thì Alex sẽ mất mặt với em gái mất!!!.

Input

• Dòng đầu tiên là ~2~ số ~N~ và ~S~.
• Dòng thứ hai gồm ~N~ số trong dãy.

Output

• Gồm ~N~ số trên ~1~ dòng, số thứ ~i~ cho biết số lần viết ít nhất số thứ tự ~i~, để hoàn thành bài tập. Vì các số có thể rất lớn nên bạn chỉ cần in ra phần dư của chúng khi chia cho ~10^{9} + 7~.

Giới hạn

• ~N \le 1\,000~, ~S \le 10\,000~, ~1 \le a_{i} \le 1\,000~
• ~60\%~ số test có ~N \le 100~.

Sample Input 1

4 3
1 1 1 2

Sample Output 1

2 2 2 3

Sample Input 2

10 5
1 1 1 1 1 1 1 1 1 1

Sample Output 2

126 126 126 126 126 126 126 126 126 126

Note

Giải thích ví dụ 1:

Các bộ số Lala phải viết: ~\{1,2,3\}, \{1,4\}, \{2,4\}, \{3,4\}~.

Nên các số ~1, 2, 3, 4~ được viết lần lượt ~2, 2, 2, 3~ lần.