There is an $n$-digit number in base $3$, initially $0$. There are $m$ types of operations. The $i$-th operation consists of choosing a partition of the set of positions $[n]$ into $S_0 \sqcup S_1 \sqcup S_2 = [n]$ such that $|S_1| = a_i$ and $|S_2| = b_i$. Then, for all positions in $S_1$, the digit is increased by $1$, and for all positions in $S_2$, the digit is increased by $2$ (all additions are modulo $3$).

Find the number of ways to perform $k$ operations such that the final number has $i$ digits equal to $1$, $j$ digits equal to $2$, and $n-i-j$ digits equal to $0$. The answer should be modulo $10^9+9$.

Input

The first line contains three integers $n, m, k$.

The next $m$ lines each contain two integers $a_i, b_i$.

Output

Output $n+1$ lines. The $i$-th line (where $0 \le i \le n$) should contain $n+1-i$ integers, where the $j$-th number (where $0 \le j \le n-i$) represents the number of ways to perform the operations such that the final number has $i$ digits equal to $1$ and $j$ digits equal to $2$.

Examples

Input 1

2 2 2
0 1
1 0

Output 1

4 2 2
2 4
2

Input 2

2 2 2
0 1
2 0

Output 2

0 0 3
6 0
0

Input 3

3 6 4
1 2
2 0
1 1
0 1
1 0
0 3

Output 3

4884 14295 14508 4873
14529 29202 14331
14313 14526
4860

Constraints

For $100\%$ of the data, $1 \le n \le 300$, $1 \le m \le 10^5$, $1 \le k \le 10^{18}$.