题目描述

这是一道模板题。

给出 $n$ 阶置换群 $S_n$ 的 $m$ 个元素。求这 $m$ 个元素生成的子群阶数。

输入格式

第一行输入两个正整数 $n, m$。

接下来 $m$ 行每行输入一个长为 $n$ 的排列，表示一个 $n$ 阶置换。

输出格式

输出一行一个正整数，表示生成子群的阶数。

样例 1

input

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

output

3628800

这两个置换可以生成整个子群。

样例 2

input

48 5
6 4 1 7 2 8 5 3 17 18 19 12 13 14 15 16 25 26 27 20 21 22 23 24 33 34 35 28 29 30 31 32 9 10 11 36 37 38 39 40 41 42 43 44 45 46 47 48
1 2 3 4 5 16 13 11 9 10 41 12 42 14 15 43 22 20 17 23 18 24 21 19 6 26 27 7 29 8 31 32 33 34 35 36 37 38 39 40 30 28 25 44 45 46 47 48
27 29 32 4 5 6 7 8 3 10 11 2 13 1 15 16 17 18 19 20 21 22 23 24 25 26 48 28 47 30 31 46 38 36 33 39 34 40 37 35 41 42 43 44 45 9 12 14
40 2 3 37 5 35 7 8 14 12 9 15 10 16 13 11 1 18 19 4 21 6 23 24 25 26 27 28 29 30 31 32 33 34 46 36 44 38 39 41 17 42 43 20 45 22 47 48
1 2 19 4 21 6 7 24 9 10 11 12 13 14 15 16 17 18 43 20 45 22 23 48 30 28 25 31 26 32 29 27 8 34 35 5 37 3 39 40 41 42 38 44 36 46 47 33

output

43252003274489856000

魔方群的阶数是 $\frac{2^{11} \times 3^7 \times 12! \times 8!}2 = 43252003274489856000$，其中的六种基本操作，可以用另外五种替代剩下的一种。

数据范围与提示

对于 $10\%$ 的数据，保证 $n\le 10$。

对于另外 $10\%$ 的数据，保证 $m = 1$。

对于 $100\%$ 的数据，保证 $n, m\le 50$。