99991337 - 呆唯和递增序列 I

通过次数

4

提交次数

10

Time Limit : 3 秒
Memory Limit : 256 MB

呆唯得到了一个 NM 列的二维数组,每个元素是一个整数。

如果从第 1 行到第 N 行,依次在每一行中选取一个数,构成长度为 N 的序列,那么一共有 M^N 种选取方案。

由于她喜欢递增的序列,她想知道:在上述的选取方案中,有多少种能使得选取出的序列是严格递增的。

由于答案可能很大,请输出答案模除 19260817 的结果。

Input

输入的第一行包含两个整数: N, M,代表数组的行数和列数 (1 \leq N, M \leq 1000)

接下来 N 行描述数组,每行输入 M 个用空格隔开的整数 x (1 \leq x \leq 10^8)。

Output

输出一个整数:从数组每一行中各取一个数,能选取出来严格递增序列的方案数。

Examples

Input

3 4
2 5 7 6
6 10 9 7
7 10 7 9

Output

18

Hint

样例中有以下 18 中选取方法:

  • 2 6 7

  • 2 6 10

  • 2 6 7

  • 2 6 9

  • 2 9 10

  • 2 7 10

  • 2 7 9

  • 5 6 7

  • 5 6 10

  • 5 6 7

  • 5 6 9

  • 5 9 10

  • 5 7 10

  • 5 7 9

  • 7 9 10

  • 6 9 10

  • 6 7 10

  • 6 7 9