Dần là một học sinh lớp 10 rất giỏi toán. Trong một tiết toán nọ, Dần được thầy giáo giao cho một bài tập:

Cho một số ~n~, tính ~2^{C_n^0} \times 2^{C_n^1} \times 2^{C_n^2} \times … \times 2^{C_n^n}~.

Dĩ nhiên, đây là một bài toán rất dễ, và Dần đã giải được nó ngay lập tức. Thầy giáo đành phải đưa ra một bài toán khó hơn chút:

Cho hai số ~n~ và ~x~, tính ~x^{C_n^0} + x^{C_n^1} + x^{C_n^2} + … + x^{C_n^n}~ (thay vì nhân thì sẽ là cộng).

Tưởng ngon ăn, Dần xung phong lên bảng làm bài. Đáng tiếc thay, sau cả buổi loay hoay, Dần vẫn chưa thể nào tính được. Các bạn hãy giúp Dần nhé.

Input

• Đọc vào hai số ~n~ và ~x~ ~(1 \leq n \leq 5 \times 10^5, 1 \leq x < 10^9+7)~

Output

• In ra ~n + 1~ số, số thứ ~i~ là ~\sum_{j=0}^{i}x^{C_n^j}~. Vì kết quả có thể rất lớn, bạn cần in kết quả modulo cho ~10^9+7~.

Sample Input

5 2

Sample Output

2 34 1058 2082 2114 2116 

Scoring