Wojtek 刚刚赢得了 Byteland 的数学竞赛!奖品令人钦佩——一本名为《适合所有人的纸牌技巧》的好书。 '伟大的!'他想,“我终于可以使用这副在我桌上一直闲置的、布满灰尘的旧纸牌了!”
这本书的第一章是“如何以您想要的任何顺序洗牌$$$k$$$”。它基本上是一系列复杂的方法,以确定的方式洗牌一副 $$$k$$$ 牌。具体来说,第 $$$i$$$ 配方可以描述为从 $$$1$$$ 到 $$$k$$$ 的整数的排列 $$$(P_{i,1}, P_{i,2}, \dots, P_{i,k})$$$。如果我们从上到下枚举这副牌中从 $$$1$$$ 到 $$$k$$$ 的牌,那么 $$$P_{i,j}$$$ 表示洗牌后从牌顶算起第 $$$j$$$ 牌的牌号。
时间很短,Wojtek 今天只想学习一些技巧。他将选择两个整数 $$$l, r$$$ ($$$1 \le l \le r \le n$$$),并且他将记住从第 $$$l$$$ 到第 $$$r$$$ 的每个技巧(包括这两个数)。然后,他会拿出一副经过排序的 $$$k$$$ 牌,并重复应用随机记忆的技巧,直到他感到无聊。他仍然喜欢数学,所以他开始想:当他停止洗牌后,他能有多少种不同的牌?
Wojtek仍然没有选择整数$$$l$$$和$$$r$$$,但他仍然很好奇。因此,他将 $$$f(l, r)$$$ 定义为如果他记住第 $$$l$$$-th 和 $$$r$$$-th 之间的所有技巧(包括这两者),他可以获得的不同牌组的数量。有什么价值
$$$$$$\sum_{l=1}^n \sum_{r=l}^n f(l, r)?$$$$$$
输入
第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le k \le 5$$$) — 技巧数和 Wojtek 牌组中的牌数。
以下 $$$n$$$ 行中的每一行都描述一个技巧,并由 $$$k$$$ 不同的整数 $$$P_{i,1}, P_{i,2}, \dots, P_{i, k}$$$ ($$$1 \le P_{i, j} \le k$$$) 描述。
输出
输出语句中描述的和的值。
示例
输入 #1
3 3 2 1 3 3 1 2 1 3 2
输出 #1
25
输入 #2
2 4 4 1 3 2 4 3 1 2
输出 #2
31
注意
考虑第一个样本:
- 第一个技巧交换两张顶牌。
- 第二个技巧从底部取出一张牌并将其放在牌堆顶部。
- 第三个技巧交换两张底牌。
第一个或第三个技巧允许 Wojtek 只生成两副不同的牌(两张牌交换或不交换)。因此,$$$f(1, 1) = f(3, 3) = 2$$$。
第二个技巧允许他以循环顺序洗牌。因此,$$$f(2,2)=3$$$。
事实证明,前两墩或最后两墩足以以 Wojtek 所需的任何方式洗牌。因此,$$$f(1,2) = f(2,3) = f(1,3) = 3! = 6$$$。