Một đồ thị hàm là một đồ thị có hướng trong đó mỗi nút có bậc ra là \(1\). Ví dụ, đây là một đồ thị hàm có \(9\) nút và \(2\) thành phần:

Cho \(n\), nhiệm vụ của bạn là tính toán với mỗi \(k = 1 \ldots n\) số lượng đồ thị hàm có \(n\) nút và \(k\) thành phần.

Input

Dòng đầu vào duy nhất chứa một số nguyên \(n\): số lượng nút.

Output

In ra \(n\) dòng: với mỗi \(k = 1 \ldots n\) số lượng đồ thị chia lấy dư cho \(10 ^ 9 + 7\).

Giới hạn

• \(1 \leq n \leq 5000\)

Ví dụ

Input:

3

Output:

17
9
1