The balls with \(1\) have the majority in every box if and only if the following holds: after repeatedly removing a pair of a ball with \(1\) and a ball with a different number, every box will have just balls with \(1\), and no box is empty.

We should exclude the balls with \(1\) to be paired with balls with other numbers beforehand, put the remaining balls with \(1\) in the boxes, and then find the product of numbers of ways to allocate the other balls to the boxes. The answer is \(\binom{a_1 - \sum_{i=2}^{N}a_i}{K+1} \prod_{i=2}^{N}\binom{a_i + K+1}{K+1}\), which can be found fast enough in \(O(NK)\) time.