communication-hard

問題文

注: この問題は「communication-easy」とほぼ同じ設定です。本文中で太字で示されている部分および制約のみが異なります。

あなたは、とある「アイドルプロデュース体験ゲーム」を遊んでいます。

このゲームでは、担当しているアイドルと「コミュニケーション」を取ることができます。
「コミュニケーション」には $N$ 回の選択パートが存在し、各パートでは次のような行動を行います。

• $i$ 回目のパートでは $K_i \, (1 \leq i \leq N)$ 個の選択肢が提示される。
• その中から $j \, (1 \leq j \leq K_i)$ 番目の選択肢を選んだ場合、コミュニケーションポイントに $S_{i,j}$ が加算される。
  • $S_{i,j}$ は整数であり、負の値を取ることもある。
  • 各選択の効果は独立しており、過去の選択に依存しない。
  • $K_i$ 個のうち、いずれかの選択肢を必ず選ばなければならない。

はじめ、コミュニケーションポイントは $0$ です。
すべての選択を終えた後、最終的なコミュニケーションポイントが $X$ 以上であれば「パーフェクトコミュニケーション」となります。

選択の総数は $\prod_{i=1}^{N} K_i$ 通りありますが、そのうち「パーフェクトコミュニケーション」となる選び方が何通りあるかを $\mod 4736947$ で求めてください。

制約

• $1 \leq N \leq 1000$
• $-10^9 \leq X \leq 10^9$
• $2 \leq K_i \leq 1000\, (1 \leq i \leq N)$
• $-3 \leq S_{i,j} \leq 3\, (1 \leq i \leq N, 1 \leq j \leq K_i)$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

「パーフェクトコミュニケーション」となる選び方が何通りあるかを $\mod 4736947$ で出力してください。

入力例 1

2 3
2 1 3
3 -3 2 0

出力例 1

3

最終的にコミュニケーションポイントが $3$ 以上となるような選び方は、$(S_{1, 1}, S_{2, 2}), (S_{1, 2}, S_{2, 2}), (S_{1, 2}, S_{2, 3})$ の $3$ 通りだけです。
よって $3$ を $4736947$ で割った余りである $3$ を出力します。

入力例 2

6 -100
20 -3 -1 -2 -1 -1 -1 3 3 2 1 2 3 1 1 1 1 2 3 3 -1
10 1 2 3 2 1 2 3 2 1 0
17 1 2 2 2 2 2 2 3 2 1 0 -1 -2 -3 1 2 3
15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
21 -3 -2 -1 0 1 2 3 2 1 -1 -2 -3 -2 -1 0 1 2 3 2 1 0

出力例 2

1401212

$\mod 4736947$ で出力することに注意してください。