选座椅

题号：NC245315
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

两人一喵终于排到售票处，准备选择放映厅的座椅。

放映厅中一共有 $n$ 张座椅，顺序拍成一排，依次编号为 $1,2,...,n$ 。由于群居效应，观影者总是会选择与其他观影者相邻的座椅，即观影者的座椅是序列 $[1,2,...,n]$ 的一段子区间。此外，两人一喵对座椅还有其他要求，分别给出了长度为 $m$ 的序列 $a,\,b$ 和 $c$ ，表示 $a_i,\,b_i$ 或 $c_i \, (1 \leq i \leq m)$ 三个座椅中至少有一个座椅被观影者使用。

记 $f(x)$ 表示放映厅中有 $x$ 位观影者的座椅使用方案数。The__Flash 想知道 $f(1),f(2),...,f(n)$ 。

由于 The__Flash 忙着跟 PLMM 贴贴，所以请你来回答这个问题。

输入描述:

第一行输入两个整数  和 。

第二行输入  个整数表示 。

第三行输入  个整数表示 。

第四行输入  个整数表示 。

输出描述:

输出  个整数，以空格分隔，分别表示 ，由于结果可能太大，所以你只需要输出结果对  取模后的结果。

示例1

输入

复制

输出

复制

2 4 6

示例2

输入

复制

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

输出

复制

1 4 12 24

示例3

输入

复制

输出

复制

0 0 12 72 480 2880 15120 80640 362880