Problem C
A Little to the Right

You’ve decided that you want to rearrange your trophy case lately. You want to order them all on a single line from left to right. However, you also want the arrangement of the trophies to be “satisfying”.

Each trophy has a certain number of properties, such as height, width, weight, etc. Each property of a trophy is measured by a positive integer. An arrangement of trophies is considered “satisfying” if at least one of these properties is strictly increasing from left to right.

(A strictly increasing sequence is one where every number in the sequence is strictly greater than the previous one.)

For example, you may want to order the trophies by strictly increasing height. Or, you may want to order the tropies by strictly increasing weight.

Given a list of trophies and their properties, output the number of satisfying arrangements there are.

Input

The first line of input contains an integer $n$ ($1 \leq n \leq 1000$), the number of trophies, and an integer $p$ ($1 \leq p \leq 50$), the number of properties each trophy has.

Each of the next $n$ lines contains $p$ space-separated integers $1 \leq c_1, c_2, \ldots , c_p \leq 10^6$. Each line represents the numerical values of each of the $p$ properties of a trophy, with the $c_i$ representing the $i^\text {th}$ property.

Output

A single integer, the number of satisfying arrangements where at least one of the properties is strictly increasing from left to right.

3 2
1 4
2 5
3 4

1

2 4
1 3 6 2
4 2 6 6

2