#4674. 模板.生成子群阶数

模板.生成子群阶数

Description

这是一道模板题。

给出 nn 阶置换群 SnS_nmm 个元素。求这 mm 个元素生成的子群阶数。

Input

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

接下来 mm 行每行输入一个长为 nn 的排列,表示一个 nn 阶置换。

Output

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

Samples

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

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

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
43252003274489856000

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

Limitation

对于 10%10\% 的数据,保证 n10n\le 10

对于另外 10%10\% 的数据,保证 m=1m = 1

对于 100%100\% 的数据,保证 n,m50n, m\le 50