时间&空间限制

Time Limit: 1.5s 2.5s

Memory Limit: 256MB

题目描述

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

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

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

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

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

1. 将$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$的大小，容易发现一共有$\cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$种分配集合的方法

2. 然后将集合$A$中的转轮转动一次，所有集合$B$中的转轮转过两次

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

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

最终，应该有$\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$ 档的方案数。

由于答案可能非常大，请输出其 $\mod 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$ 档的方案数，$\mod 10^9+9$。

输入输出样例

​ machine1.in

2 2 2
0 1
1 0

​ machine1.out

4 2 2
2 4
2

​ machine2.in

2 2 2
0 1
2 0

​ machine2.out

0 0 3
6 0
0

​ machine3.in

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

​ machine3.out

4884 14295 14508 4873
14529 29202 14331
14313 14526
4860

样例解释

对于样例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

数据规模与约定

本题不采用子任务评测。

对于所有数据，满足 $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$的上限以及数据的特殊性质：