ビットDP 練習問題 1 Python2編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 商店には N 種類の商品があります。
あなたは無料引換券を M 枚もっており、i 枚目の券を使うと商品 A_{i,1}, A_{i,2}, ... , A_{i,k_i} を 1 つずつもらうことができます。
いくつかの引換券を組み合わせることで、すべての商品を 1 つ以上手に入れたいです。
すべての商品を 1 つ以上手に入れることができるような引換券の組合せはいくつありますか？
答えは非常に大きくなる可能性があるため、10^9 で割ったあまりを出力してください。
入力例 1 では、例えば、1 枚目と 5 枚目の引換券を使うことで 3 種類すべての商品を手に入れることができます。
このような 3 種類すべての商品を手に入れることができる引換券の組合せは 25 通りあるため、25 を出力します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N M
k_1 A_{1,1} A_{1,2} ... A_{1,k_1}
k_2 A_{2,1} A_{2,2} ... A_{2,k_2}
...
k_M A_{M,1} A_{M,2} ... A_{M,k_M}
・ 1 行目には、商品の種類を表す整数 N と引換券の数を表す整数 M が空白区切りで与えられます。
・ 続く M 行には、i 枚目の引換券で手に入れることができる商品数 k_i と引き換えできる k_i 個の商品 A_{i,j} (1 ≦ j ≦ k_i) が空白区切りで与えられます。
・ 入力は合計で 1 + M 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
すべての商品を 1 つ以上手に入れることができるような引換券の組合せの数を 10^9 で割ったあまりを出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 14
・ 1 ≦ M ≦ 500
・ 1 ≦ k_i ≦ N
・ 1 ≦ A_{i,1} < A_{i,2} < ... < A_{i,k_i} ≦ N
- 入力例1
-
3 5
2 1 2
3 1 2 3
2 1 3
1 3
2 2 3
- 出力例1
-
25
- 入力例2
-
10 3
3 1 2 3
3 4 5 6
3 7 8 9
- 出力例2
-
0
- 入力例3
-
3 30
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
- 出力例3
-
73741823
