## COCI '11 Contest 6 #6 Košare

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Mirko found boxes with various forgotten toys in his attic. There are different toys, numbered through , but each of those can appear multiple times across various boxes.

Mirko decided that he will choose some boxes in a way that there is at least one toy of each kind present, and throw the rest of the boxes away.

Determine the number of ways in which Mirko can do this.

#### Input Specification

The first line of input contains two integers and . Each of the following lines contains an integer followed by distinct integers from the interval , representing the toys in that box.

#### Output Specification

The first and only line of output should contain the requested number of ways modulo .

#### Scoring

In test cases worth 50% of total points, and will hold.

In test cases worth 70% of total points, and will hold.

#### Sample Input 1

3 3
3 1 2 3
3 1 2 3
3 1 2 3

#### Sample Output 1

7

#### Sample Input 2

3 3
1 1
1 2
1 3

#### Sample Output 2

1

#### Sample Input 3

4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5

#### Sample Output 3

6