Một đồ thị giải đấu là một đồ thị có hướng, trong đó giữa mỗi cặp đỉnh luôn có đúng một cạnh có hướng.

Cho \(n\), nhiệm vụ của bạn là tính, với mỗi \(k = 1 \dots n\), số đồ thị giải đấu có \(n\) đỉnh và \(k\) thành phần liên thông mạnh.

Input

Dòng duy nhất chứa một số nguyên \(n\): số lượng đỉnh.

Output

In ra \(n\) dòng: với mỗi \(k=1 \dots n\), số đồ thị tương ứng lấy modulo \(10^9+7\).

Constraints

• \(1 \le n \le 500\)

Example

3

2
0
6