Trong chương trình toán lớp 1 năm 2066, sau khi học xong lí thuyết tổ hợp cơ bản, các em học sinh đã hiểu được

số tập con khác rỗng của một tập hợp có \(N\) phần tử là \(2^N - 1\).

Nếu việc học chỉ dừng lại ở phần đọc, hiểu và nhớ lí thuyết thì chắc chắn sẽ không đem lại sự hứng thú cho các em học sinh và không củng cố được tư duy toán học cho các em học sinh. Vì vậy ở phần bài tập của sách giáo khoa có một bài tập như sau:

Cho \(N\) đồ chơi được sắp xếp thành một hàng ngang, các đồ chơi được đánh số từ \(1\) đến \(N\), đồ chơi thứ \(i\) (\(1 \leq i \leq N\)) từ trái sang phải được đánh số là \(i\).

Gọi khoảng cách giữa hai đồ chơi thứ \(i\) (\(1 \leq i \leq N\)) và thứ \(j\) (\(1 \leq j \leq N\)) là \(\lvert i - j \rvert\). Một cách chọn ra ít nhất một đồ chơi trong \(N\) đồ chơi tương ứng với một tập con khác rỗng của tập hợp \(N\) đồ chơi. Một cách chọn được gọi là \(k\) - xa cách khi và chỉ khi

• có ít nhất một đồ chơi được chọn và
• bất kì hai đồ chơi khác nhau được chọn đều có khoảng cách không bé hơn \(k\).

Với mỗi số nguyên \(k\) (\(1 \leq k \leq N\)), bài tập yêu cầu học sinh đưa ra số cách chọn \(k\) - xa cách, lấy phần dư khi chia cho \(10^9 + 7\).

Yêu cầu: Hãy lập trình để tìm ra đáp án chính xác của bài toán, để làm lời giải cho các em học sinh đối chiếu đáp án.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \leq N \leq 10^5\)).

Output

• Gồm \(N\) dòng, dòng thứ \(k\) (\(1 \leq k \leq N\)) gồm một số nguyên là số cách chọn \(k\) - xa cách, lấy phần dư khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(N \leq 20\).
• Subtask \(2\) (\(15\%\) số điểm): \(N \leq 300\).
• Subtask \(3\) (\(25\%\) số điểm): \(N \leq 5000\).
• Subtask \(4\) (\(45\%\) số điểm): Không có ràng buộc gì thêm.

Example

1

1

2

3
2

3

7
4
3