Şehmettin just bought \(\mathbf{N}\) Yu-Gi-Oh cards but since he was a tasteless person he decided to sell them to his friends instead of playing with them.

To sell the Yu-Gi-Oh cards, Şehmettin decided to put them into surprise packs. Şehmettin wonders how many surprise pack combinations there are. However, he wants to know how many combinations there are when the cards are grouped into different numbers of packs \(\mathbf{X}\) from \(\mathbf{1}\) to \(\mathbf{N}\), inclusive. In other words, how many different ways he could sell the cards he has if he had \(\mathbf{X = 1}\) pack, \(\mathbf{X = 2}\) packs, \(\dots\) , \(\mathbf{X = N - 1}\) packs, \(\mathbf{X = N}\) packs?

• There can be a different number of cards in surprise packs but each pack will at least have 1 card.
• Every card is unique.
• Since these numbers can be quite big, print the number of combinations modulo \(10^9+7\).

Input

The input contains 1 integer \(\mathbf{N}\), the number of Yu-Gi-Oh cards.

• \(1 \leq \mathbf{N} \leq 1000\)

Output

The output contains \(\mathbf{N}\) integers in a single line.

• Number of different surprise pack combinations for surprise pack number \(\mathbf{X}\) from \(1\) to \(\mathbf{N}\) (print modulo \(10^9+7\))

Example

Input:

3

Output:

1 3 1

Explanation

Input 1

For 3 cards there are 1 3 1 combinations in total which are:

• 1 combination when the cards are grouped into 1 surprise pack: \(\{(1,2,3)\}\in G_1\)
• 3 combinations when the cards are grouped into 2 surprise packs: \(\{(1,2),(3)\},\{(1,3),(2)\},\{(1),(2,3)\}\in G_2\)
• 1 combination when the cards are grouped into 3 surprise packs: \(\{(1),(2),(3)\}\in G_3\)