Problem B
Ballfoot Battles

You love the sport of ballfoot. It is the futuristic version of football where many teams can play at once! There is still only one ball, so one goal is scored at the time, and each team starts with zero goals. Being busy completing the mandatory assignments for your algorithms and datastructures course, you unfortunately do not have time to watch todays game between all of your $T$ favorite teams!

The best you can do is check your futuristic phone from time to time and see what the current score is. You will therefore know the score at $N$ arbitrary moments in the match, and you always check what the final result is. Having seen the scoreboard a few times throughout the match makes you wonder, in how many ways could the match have been played? This question is about how many ways the game could have gone in terms of the order of which team scores which goal. If one team wins four to zero, it must have been 4 goals in a row for that team. If a team wins two to one, there are three different sequences of goals that could reach that outcome.

Input

The first line contains two integers. $T$ describes the number of teams participating in the match. $N$ describes the number of times you check you phone and peek at the score. Then follows $N$ lines, each of which containing the $T$ integers $g_{t,n}$, which is the number of goals team $t$ has at time point $n$ in the match. The last observation is always the final scoreline.

Output

Output the number of ways the match could have given the observations. The answer can be very large, so output the result modulo $10^9+7$.

Limits

• $1 \leq T \leq 100$

• $1 \leq N \leq 1000$

• $1 \leq g_{t,n} \leq 50000$

3 4
0 1 2
0 3 2
2 3 2
3 3 2

3