Permutation MEX Parity

You are given a positive integer n. Consider all permutations a of the set {0,1,…,n-1}. For each permutation a, define a set S(a) as follows. For every element x in the permutation, let cnt(x) be the number of contiguous subarrays of a in which the minimum element is x. Then x is included in S(a) if and only if cnt(x) is odd.

Define the function mex(S) to be the smallest non-negative integer that is not in the set S. In other words,

$$\operatorname{mex}(S)=\min\{x\in \mathbb{N}:x\notin S\}.$$

Your task is: for each i = 0,1,2,\dots,n, compute the number of permutations a of {0,1,…,n-1} for which mex(S(a)) = i. Since the answer may be large, output it modulo 10^9+7.

How to compute cnt(x) in a permutation?
For a permutation a of length n, for each index i (0-indexed), let a[i] = x. Let left be the number of consecutive positions (including position i) to the left of i until (but not including) an element smaller than a[i] appears. Formally, let p be the index of the previous element that is smaller than a[i] or -1 if none exists; then L = i - p.
Similarly, let R be the number of consecutive positions (including i) to the right of i until an element smaller than a[i] is encountered (or the end of the array). That is, if q is the index of the next element smaller than a[i] (or n if none exists), then R = q - i.
Then, cnt(x) for that occurrence is L * R and x is in S(a) if and only if L * R is odd.

Definition of mex: For a set S of non-negative integers, mex(S) is defined as:

$$\operatorname{mex}(S)=\min\{x\in \mathbb{N}:x\notin S\}.$$

Input: A single integer n representing the size of the permutation.

Output: Output n+1 space‐separated integers. The i-th integer (0 ≤ i ≤ n) should be the number of permutations a with mex(S(a)) = i, taken modulo 10^9+7.

inputFormat

The input consists of a single line containing an integer n (1 ≤ n ≤ ?). (Note: Due to the computational complexity of enumerating all permutations, you may assume n is small enough for a brute force solution.)

outputFormat

Output a single line with n+1 integers, where the i-th integer represents the count (modulo 10^9+7) of permutations a such that mex(S(a)) = i.

sample

1

0 1