题目描述

奆 $\mathscr{L}$ 有一个神秘的抽奖机，它由 $n$ 个转轮组成。

每个转轮有三个档位，记作 $0,1,2$，转轮的转动与档位关系如下：

• 当一个 $0$ 档位转轮被转过一次，会变成 $1$ 档位。
• 当一个 $1$ 档位转轮被转过一次，会变成 $2$ 档位。
• 当一个 $2$ 档位转轮被转过一次，会变成 $0$ 档位。

一开始所有 $n$ 个转轮都在 $0$ 档，将所有转轮的集合记作 $S$。

抽奖机的抽奖器有 $m$ 个模式，每个模式可以用两个数字 $a_i,b_i$ 描述，表示：

• 将 $S$ 分为三个集合 $A,B,C$，即满足： $A\cap B,A\cap B,B\cap C=\emptyset,A\cup B\cup C=S,|A|=a_i,|B|=b_i$ 其中 $|A|$ 表示集合 $A$ 的大小，容易发现一共有 $\displaystyle \cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$ 种分配集合的方法
• 然后将集合 $A$ 中的转轮转动一次，所有集合 $B$ 中的转轮转过两次

每次拉下摇杆，抽奖机都会进行转动，一次转动如下：

• 从所有模式里选取一个进行；
• 从所有可能的转动情况中选择一个进行。

最终，应该有 $\displaystyle \sum_{i=1}^m \cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$ 种方案，在这样的所有方案中选择一个。

现在奆 $\mathscr{L}$ 通过 py 手段得知了所有的模式，但是 ta 依然无法控制抽奖机的结果。

自暴自弃的 ta 决定连续乱拉 $k$ 次拉杆，而并且在此之前，ta 暴怒地逼问你：

最终抽奖机恰好有 $i$ 个转轮在 $1$ 档，$j$ 个转轮在 $2$ 档的方案数。

由于答案可能非常大，请输出其 $\bmod 10^9+9$ 的结果。

输入格式

第一行三个正整数 $n,m,k$，表示转轮个数，模式个数，奆 $\mathscr{L}$ 拉拉杆的次数。

然后 $m$ 行，每行两个整数 $a_i,b_i$，描述奆 $\mathscr{L}$ 通过 py 得知的一个模式。

输出格式

输出 $n+1$ 行，第 $i$ 行输出 $n+2-i$ 个数。

第 $i$ 行第 $j$ 个数表示：最终抽奖机恰好有 $i$ 个转轮在 $1$ 档，$j$ 个转轮在 $2$ 档的方案数，$\bmod 10^9+9$。

样例 1

输入

2 2 2
0 1
1 0

输出

4 2 2
2 4
2

对于样例 1，容易发现一次有 $4$ 种可能 $01,10,02,20$

两次一共有 $16$ 种可能：

• $01 \rightarrow 02,11,00,21$
• $10 \rightarrow 11,20,21,00$
• $02 \rightarrow 00,12,01,22$
• $20 \rightarrow 21,00,22,10$

样例 2

输入

2 2 2
0 1
2 0

输出

0 0 3
6 0
0

样例 3

输入

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

输出

4884 14295 14508 4873
14529 29202 14331
14313 14526
4860

数据范围与提示

本题不采用子任务评测。

对于所有数据，满足 $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$。

给定的 $m$ 个模式之间可能有重复。

下表列出了所有 $20$ 个测试点 $n,m,k$ 的上限以及数据的特殊性质：

#	$n$	$m$	$k$	特殊性质
1	$3$	$6$	$4$	无
2	$5$	$10$
3	$8$	$3$	$5$
4	$20$
5	$17$	$500$	$10^9$
6	$20$		$10^{18}$
7	$40$	$10^5$	$20$	$b_i=0$
8			$10^9$
9	$50$			无
10	$40$	$10^5$	$10^{9}$
11	$50$		$10^{18}$
12	$10$			$b_i=0$
13	$80$	$100$
14	$100$
15			$10^{9}$	无
16		$10^5$
17			$10^{18}$
18	$110$
19	$120$