Bạn được cho một mảng chứa mỗi số từ \(1 \dots n\) đúng một lần. Bạn thu thập các số theo thứ tự tăng dần từ \(1\) đến \(n\). Ở mỗi vòng, bạn duyệt mảng từ trái sang phải và thu thập nhiều số liên tiếp nhất có thể, bắt đầu từ số nhỏ nhất chưa được thu thập.

Nhiệm vụ của bạn là xác định, với mỗi \(k=1,2,\dots,n\), số mảng cần đúng \(k\) vòng để thu thập tất cả các số.

Input

Dòng duy nhất chứa một số nguyên \(n\).

Output

In ra \(n\) số: với mỗi \(k=1,2,\dots,n\), đáp án lấy modulo \(10^9+7\).

Constraints

• \(1 \le n \le 5000\)

Example

3

1
4
1

Explanation

Các mảng là \([1,2,3]\) (\(1\) vòng), \([1,3,2]\) (\(2\) vòng), \([2,1,3]\) (\(2\) vòng), \([2,3,1]\) (\(2\) vòng), \([3,1,2]\) (\(2\) vòng), và \([3,2,1]\) (\(3\) vòng).