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\).

Constraints

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

Example

3

17
9
1