The great $\mathscr{L}$ has a mysterious lottery machine consisting of $n$ wheels.

Each wheel has three positions, denoted as $0, 1, 2$. The rotation of a wheel and its position change as follows:

1. When a wheel at position $0$ is rotated once, it becomes position $1$.
2. When a wheel at position $1$ is rotated once, it becomes position $2$.
3. When a wheel at position $2$ is rotated once, it becomes position $0$.

Initially, all $n$ wheels are at position $0$. Let $S$ be the set of all wheels.

The lottery machine has $m$ modes. Each mode is described by two numbers $a_i, b_i$, which mean:

1. Divide $S$ into three sets $A, B, C$ such that:

   • $A \cap B = \emptyset, A \cap C = \emptyset, B \cap C = \emptyset, A \cup B \cup C = S, |A| = a_i, |B| = b_i$.

     Here, $|A|$ denotes the size of set $A$. It is easy to see that there are $\frac{n!}{a_i!b_i!(n-a_i-b_i)!}$ ways to distribute the wheels into these sets.

2. Then, rotate the wheels in set $A$ once, and rotate the wheels in set $B$ twice.

Every time the lever is pulled, the machine performs a rotation, which consists of:

1. Choosing one mode from all available modes.
2. Choosing one way to distribute the wheels from all possible distributions for that mode.

Ultimately, there are $\sum_{i=1}^m \frac{n!}{a_i!b_i!(n-a_i-b_i)!}$ possible outcomes for a single pull, and one is chosen from these.

Now, the great $\mathscr{L}$ has learned all the modes through "py" means, but still cannot control the machine's result.

In despair, $\mathscr{L}$ decides to pull the lever $k$ times randomly, and before doing so, $\mathscr{L}$ furiously demands that you calculate:

The number of ways such that the final machine has exactly $i$ wheels at position $1$ and $j$ wheels at position $2$.

Since the answer may be very large, output the result modulo $10^9+9$.

Input

The first line contains three positive integers $n, m, k$, representing the number of wheels, the number of modes, and the number of times $\mathscr{L}$ pulls the lever.

Then $m$ lines follow, each containing two integers $a_i, b_i$, describing a mode $\mathscr{L}$ learned.

Output

Output $n+1$ lines. The $i$-th line should contain $n+2-i$ numbers.

The $j$-th number in the $i$-th line represents the number of ways the final machine has exactly $i-1$ wheels at position $1$ and $j-1$ wheels at position $2$, modulo $10^9+9$.

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

Note

For Example 1, it is easy to see that there are $4$ possibilities for one pull: 01, 10, 02, 20.

There are $16$ possibilities for two pulls:

01 $\rightarrow$ 02, 11, 00, 21

10 $\rightarrow$ 11, 20, 21, 00

02 $\rightarrow$ 00, 12, 01, 22

20 $\rightarrow$ 21, 00, 22, 10

Constraints

For all data, $n \leq 120, m \leq 10^5, k \leq 10^{18}, \forall 0 \leq a_i, b_i \leq n, \forall a_i+b_i \leq n$.

The given $m$ modes may contain duplicates.

The following table lists the upper bounds for $n, m, k$ and special properties for all 20 test cases: