問題一覧 > 通常問題

No.1763 Many Balls

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan tokusakuraitokusakurai
0 ProblemId : 7111 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-20 02:21:20

問題文

$N$ 個の区別可能なボールを $M$ 人の人に配ります。ただし、誰にも配られないボールがあってもいいです。

ここで、条件 $X_i$ を「配られたボールの個数が $i$ の倍数であること」と定義します。

$M$ 人の人はわがままなので、$i$ 番目の人は $X_{A_{i,1}},X_{A_{i,2}},...,X_{A_{i,k_i}}$ の条件の内少なくとも $1$ 個を満たさないと怒ってしまいます。また、条件を $1$ 個以上満たせば怒ることはありません。

誰も怒らないようなボールの配り方を $\boldsymbol{90001}($素数$)$ で割ったあまりを求めてください。

制約

  • 入力は全て整数である。
  • $1 \le N \le 10^{200000}$
  • $1 \le M \le 10$
  • $1 \le k_i \le 6$
  • $1 \le A_{i,j} \le 6$

入力

$N\ M$
$k_1\ A_{1,1}\ A_{1,2}\ \dots A_{1,k_1}$
$k_2\ A_{2,1}\ A_{2,2}\ \dots A_{2,k_2}$
$\vdots$
$k_M\ A_{M,1}\ A_{M,2}\ \dots A_{M,k_M}$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
4 2
1 2
1 1
出力
41

ボールの配り方として、人 $1$ にボール $2,3$ を配り人 $2$ にボール $4$ を配るなどの $41$ 通りがあります。

サンプル2
入力
10 3
1 2
1 3
2 2 3
出力
36952

サンプル3
入力
2021 6
1 1
2 2 3
3 4 5 6
1 6
2 4 5
3 1 2 3
出力
83960

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。