明らかに次の条件は必要です。

• (1) \(\sum_i A_i = \sum_i B_i = M\)
  
• (2) \(\sum_i \min(A_i, B_i) \ge X\)
  

\(i \ne j\) である操作回数を \(Y:=M-X\) とします。 \(X=0\) の場合を考えると、一回の操作で各 \(A_i+B_i\) は高々 \(1\) しか増えないため、

• (3’) \(A_i+B_i \le Y\ \mathrm{for\ all}\ i\)

も必要です。Hall の定理より (1),(2),(3’) で十分条件にもなります。

\(X>0\) の場合は代わりに次の条件が必要になります。

• (3) \(i\) を選択して \(A_i,B_i\) の値を \(1\) ずつ減らす、という操作を \(X\) 回以下行うことで条件 (3’) を満たせる

ここまでの (1),(2),(3) が必要十分条件です。

(1),(2) を満たす \(A,B\) の数と、(1),(2) は満たすが (3) は満たさない \(A,B\) の数がそれぞれ求まれば本問題の答えが得られます。前者に関しては、 \(A_i>B_i\) である \(i\) の数と \(\sum_i \min(A_i, B_i)\) の値で場合分けすることで \(O(NM)\) で計算できます。以下、後者を考えます。

(1),(2) より \(|A_i-B_i| \le Y\) が示せるため、(3) において「操作は \(X\) 回以下」という条件を無視すれば必ず (3’) を満たすようにできます。この最小操作回数が \(X+1\) 以上であるものを数えればよいです。

最小の操作で (3’) を満たすようになった後の数列を \(A',B'\) とします。操作が行われた可能性がある \(i\) は \(A'_i+B'_i\) が \(Y-1\) または \(Y\) となっている箇所です。操作は \(X+1\) 回以上行われたことから \(\sum_i A'_i = \sum_i B'_i \le Y - 1\) であることを踏まえると、 \(Y \ge 2\) の場合は次の \(3\) 通りを考えればよいです（割愛するが \(Y=0,1\) の場合に注意）。

• \(A'_i+B'_i=Y\) である \(i\) が \(1\) つ、他は \(A'_i+B'_i \le Y-2\)
• \(A'_i+B'_i=Y-1\) である \(i\) が \(1\) つ、他は \(A'_i+B'_i \le Y-2\)
• \(A'_i+B'_i=Y-1\) である \(i\) が \(2\) つ、他は全て \(0\)

これらの \(A',B'\) になる元の \(A,B\) を数えればよく、 \(O(M)\) で計算できます。

以上より \(O(NM)\) でこの問題に答えることができます。