Problem Description
Given an integer A, an array Z of integers of size A contains all the numbers from 1 to A. Now there can be many different permutations of this array. For a particular X, if Zi = i for exactly X different i from 1 to A, the permutation is called X-Permutation. For each X from 0 to A, find the number of X-Permutations for each X modulo 1000000007.
Problem Constraints
1 <= A <= 105
Input Format
The first argument is an integer A.
Output Format
Return an integer array of size A+1 where each element is the number of X-Permutations.
Example Input
Input 1:
A = 3
Input 2:
A = 1
Example Output
Output 1:
[2, 3, 0, 1]
Output 2:
[0, 1]
Example Explanation
For Input 1:
For X=0, permutations [3, 1, 2] and [2, 3, 1] satisfy.
For X=1, permutations [1, 3, 2], [2, 1, 3], and [3, 2, 1] satisfy.
For X=2, no permutation satisfies.
For X=3, permutation [1, 2, 3] satisfies.
For Input 2:
For X=0, no permutation satisfies.
For X=1, permutation [1] satisfies.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified.
Still have a question? Checkout Sample Codes for more details.