19023번 - Good Game 다국어

You want to walk from $(0, 0, \ldots, 0)$ to $(a_0, a_1, \ldots, a_{n - 1})$ in an $n$-dimensional space. On each step, you can increase one component of your coordinate vector by one. There are $m$ obstacles $p_1, p_2, \ldots, p_m$. You want to find the number of paths that don't pass through the obstacles.

However, this problem is too simple for an ICPC contest in the year 8102. We add one more constraint. For every point $(x_0, x_1, \ldots, x_{n - 1})$ on your path, the components of this vector should be non-decreasing: $x_0 \leq x_1 \leq \ldots \leq x_{n - 1}$.

Output the number of paths modulo $10^9 + 7$.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 50$, $0 \leq m \leq 50$).

The second line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($0 \leq a_0 \leq a_1 \leq \ldots \leq a_{n-1} \leq 10^4$), the coordinate vector of your destination.

The following $m$ lines describe obstacles. The $i$-th of these lines contains $n$ integers $p_{i, 0}, p_{i, 1}, \ldots, p_{i, n - 1}$ ($0 \leq p_{i, 0} \leq p_{i, 1} \leq \ldots \leq p_{i, n - 1} \leq 10^4)$, the coordinate vector of an obstacle.

The starting point, destination, and all the obstacles are distinct.

Output the answer modulo $10^9 + 7$.