排列组合(二)

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

有N个字母,每个字母的数量不定。用这N个字母组成一个长为M的串,并且规定这个串中每个字母能出现的次数。求这样的串的总数。

Input

每组输入数据的第一行有两个数字N,M。接下来有N行,每行的第一个数k表示对应字母可以出现的种数,接下来的k个数表示该字母可以在串中出现的个数。其中0表示可以不出现。如测试数据,第一个2表示有"A""B"两个字母,第二个2表示求一个长度为2的串,第二行的第一个数3表示后面有3个数字,0,1,2分别表示字母"A"在这个串中可以出现0次,1次,2次,第三行表示字母"B"可以出现的次数。则这样的串有"AB","BA","AA"3种。

Output

对应每组输入,输出满足要求的串的总数。(输出结果不会超出2^63)

Sample Input

2 2 3 0 1 2 2 0 1

Sample Output

3

Hint

lcy

Source

ACM暑期集训队练习赛(四)

提交代码