Bài toán này của chúng ta nói về infrmtcs, hay còn được giang hồ đồn đại với tên gọi DĐạt(đọc thế nào tùy các bạn, có thể là Dương Đạt theo tên gốc hay là Dê Đạt cũng được). Dù nổi tiếng xấu trai nhưng do chém gió giỏi nên anh ta thường xuyên tổ chức các buổi tiệc lớn để nâng cao khả năng chém gió cũng như tăng cơ hội để tiếp cận với Princess KH, người mà anh ta thầm yêu từ lâu. Để ấm cúng, tất cả mọi người tham gia bữa tiệc sẽ ngồi trên một chiếc bàn tròn với kích cỡ rất lớn. Về các khách mời, infrmtcs quyết định mời đến bữa tiệc ~N~ cặp đôi (2xN người). Tuy nhiên được biết trong đó có ~1~ số cặp đôi anh không thích họ đi với nhau, có thể là do ~1~ trong số họ từng đá xoáy anh hoặc cặp đôi có lệch lạc về giới tính. Do đó, anh quyết định tách họ ra bằng cách không cho họ ngồi cạnh nhau. infrmtcs muốn tính xem có bao nhiêu cách xếp ~N~ cặp đôi vào chiếc bàn tròn sao cho có đúng ~K~ cặp đôi ngồi cạnh nhau. Tuy nhiên infrmtcs đang bận đi mua gấu bông cho KH, nên anh quyết định nhờ bạn tính hộ. Nhiệm vụ của bạn là tính số cách với tất cả các ~K = 0~ ...~N~. Do các số có thể rất lớn nên bạn chỉ cần in ra phần dư của kết quả cho ~1000000007~.

Input

• Một dòng duy nhất ghi số nguyên dương ~N~.

Output

• Ghi trên ~1~ dòng duy nhất ~N + 1~ số ~p_{0}~ ...~p_{N}~ tương ứng với có ~p_{K}~ cách xếp cho mỗi giá trị ~K~

Giới hạn

• ~1 \leq N \leq 1000~

Sample Input 1

2

Sample Output 1

2 0 4

Sample Input 2

3

Sample Output 2

32 48 24 16

Note

Update: nói rõ hơn: các cách sinh ra nhờ hoán vị vòng quanh đều chỉ tính là 1 cách.