731. Nth Row of Pascal's Triangle (Modulo 10^9+7)

Given a non-negative integer n, return the n-th row of Pascal's Triangle (0-indexed) as a single string of numbers separated by single spaces. Row 0 is "1", row 1 is "1 1", row 2 is "1 2 1", and so on. Each entry is a binomial coefficient C(n, k), and because these values can grow very large, return each entry modulo 10^9 + 7. Implement the construction using a recursive definition: row n can be derived from row n-1 by summing each pair of adjacent entries (treating out-of-bounds positions as 0), all taken modulo 10^9 + 7.

Input: A single non-negative integer n.

Output: A space-separated string of integers (each mod 10^9 + 7) representing row n.

Examples

Input: 0
Output: 1
Explanation: Row 0 is [1].

Input: 3
Output: 1 3 3 1
Explanation: C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1; all less than MOD so unchanged.

Input: 5
Output: 1 5 10 10 5 1
Explanation: Row 5 of Pascal's Triangle.

Constraints

• 0 <= n <= 10^3

Asked by