AT_abc128_c [ABC128C] Switches

Description

[problemUrl]: https://atcoder.jp/contests/abc128/tasks/abc128_c on と off の状態を持つ $ N $ 個の スイッチと、$ M $ 個の電球があります。スイッチには $ 1 $ から $ N $ の、電球には $ 1 $ から $ M $ の番号がついています。 電球 $ i $ は $ k_i $ 個のスイッチに繋がっており、スイッチ $ s_{i1},\ s_{i2},\ ...,\ s_{ik_i} $ のうち on になっているスイッチの個数を $ 2 $ で割った余りが $ p_i $ に等しい時に点灯します。 全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

Input Format

N/A

Output Format

N/A

Explanation/Hint

### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 10 $ - $ 1\ \leq\ k_i\ \leq\ N $ - $ 1\ \leq\ s_{ij}\ \leq\ N $ - $ s_{ia}\ \neq\ s_{ib}\ (a\ \neq\ b) $ - $ p_i $ は $ 0 $ または $ 1 $ - 入力は全て整数である ### Sample Explanation 1 \- 電球 $ 1 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1,\ 2 $ - 電球 $ 2 $ は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ $ 2 $ (スイッチ $ 1 $、スイッチ $ 2 $) の状態としては (on,on),(on,off),(off,on),(off,off) が考えられますが、このうち (on,on) のみが条件を満たすので、$ 1 $ を出力してください。 ### Sample Explanation 2 \- 電球 $ 1 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1,\ 2 $ - 電球 $ 2 $ は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ $ 1 $ - 電球 $ 3 $ は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ $ 2 $ 電球 $ 2 $ を点灯させるためには スイッチ $ 1 $ が off, 電球 $ 3 $ を点灯させるためにはスイッチ $ 2 $ が on である必要がありますが、この時電球 $ 1 $ は点灯しません。 よって、全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは存在しないので、$ 0 $ を出力してください。