有一个 $n$ 位 $3$ 进制数，一开始为 $0$，有 $m$ 种操作，第 $i$ 种操作是选择一个集合划分 $S_0 \sqcup S_1 \sqcup S_2 = [n]$，满足 $|S_1| = a_i$ 且 $|S_2| = b_i$，然后将 $S_1$ 集合里的位都加上 $1$，$S_2$ 集合里的位都加上 $2$。

问经过 $k$ 次操作之后，总共有多少种操作方式让数最后有 $i$ 个 $1$，$j$ 个 $2$（以及 $n-i-j$ 个 $0$）。答案对 $10^9+9$ 取模。

Input

第一行三个整数 $n,m,k$。

接下来 $m$ 行，每行两个整数 $a_i,b_i$。

Output

输出 $n+1$ 行，第 $i$ 行输出 $n+2-i$ 个数，表示有多少种操作方式让数最后有 $i$ 个 $1$，$j$ 个 $2$（以及 $n-i-j$ 个 $0$）。

Samples

Input

2 2 2
0 1
1 0

Output

4 2 2
2 4
2

Input

2 2 2
0 1
2 0

Output

0 0 3
6 0
0

Input

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

Output

4884 14295 14508 4873
14529 29202 14331
14313 14526
4860

Limitation

对 $100\%$ 的数据，保证 $1\le n\le \color{red}{\mathbf{300}}, 1\le m\le 10^5, 1\le k\le 10^{18}$。