题目描述

奆 $\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$。

2 2 2
0 1
1 0

4 2 2
2 4
2

2 2 2
0 1
2 0

0 0 3
6 0
0

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$	$10$
$3$	$8$	$3$	$5$
$4$	$20$	$20$	$20$
$5$	$17$	$500$	$10^9$
$6$	$20$		$10^{18}$
$7$	$40$	$10^5$	$20$	$b_i=0$
$8$			$10^9$
$9$	$50$	$50$		无
$10$	$40$	$10^5$	$10^{9}$
$11$	$50$		$10^{18}$
$12$			$10$	$b_i=0$
$13$	$80$		$100$
$14$	$100$
$15$		$100$	$10^{9}$	无
$16$		$10^5$
$17$			$10^{18}$
$18$	$110$
$19$
$20$	$120$