跳至正文
题库2826
#2826

Deja Vu

查看题目操作

Deja Vu

本站版本:子任务 E2(计数)

本站测试文件采用原题 E2 的计数版本。对每种长度 1 到 2n,依次输出符合条件的路径数,答案模 1000000007。原题 E1 的路径构造格式不适用于本站本题。

题目描述

Everybody knows that we have been living in the Matrix for a long time. And in the new seventh Matrix the world is ruled by beavers.

So let's take beaver Neo. Neo has so-called "deja vu" outbursts when he gets visions of events in some places he's been at or is going to be at. Let's examine the phenomenon in more detail.

We can say that Neo's city is represented by a directed graph, consisting of n shops and m streets that connect the shops. No two streets connect the same pair of shops (besides, there can't be one street from A to B and one street from B to A). No street connects a shop with itself. As Neo passes some streets, he gets visions. No matter how many times he passes street k, every time he will get the same visions in the same order. A vision is a sequence of shops.

We know that Neo is going to get really shocked if he passes the way from some shop a to some shop b, possible coinciding with a, such that the list of visited shops in the real life and in the visions coincide.

本站采用原题子任务 E2:请统计每种长度的合法路径数量,答案模 1000000007。

Input

The first line contains integers n and m − the number of shops and the number of streets, correspondingly, 1≤n≤50, . Next m lines contain the descriptions of the streets in the following format: xi yi ki v1 v2 ... vk, where xi and yi (1≤xi,yi≤n,xi≠yi) are numbers of shops connected by a street, ki (0≤ki≤n) is the number of visions on the way from xi to yi; v1, v2, ..., vk (1≤vi≤n) describe the visions: the numbers of the shops Neo saw. Note that the order of the visions matters.

It is guaranteed that the total number of visions on all streets doesn't exceed 105.

本站仅评测子任务 E2 的计数输出。

Output

Subproblem E2. Print 2·n lines. The i-th line must contain a single integer − the number of required paths of length i modulo 1000000007 (109+7).

Examples

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

Note

The remaining sample is the counting answer for subproblem E2.