Answer在看过碟中谍后，对“X中X”很感兴趣，于是想探究“图中图”。
“图中图”的外图是一张由M个大节点组成的有K条边(无重边和自环)的无向无权图(不一定连通)，外图中的每个大节点的内部又是一张由若干条边组成的无向有权图。
Answer想要构一张“图中图”，对大节点之间的边可以随便连K条，对每个大节点内部的无向图，Answer有一种生成方法：
1. 先确定一个长度为N的序列A
2. 对于每个大节点，确定一个在A中的区间[l_i , r_i]
3. 那么在第i个大节点中，
边数=sigma(sum_x+num_x³) 区间[l_i , r_i]中存在x
其中sum_x为在区间[l_i , r_i]中比x小的数字个数，num_x为区间[l_i , r_i]中等于x的数字个数。
设t为在区间[l_i , r_i ]中出现的不重复的数字个数，那么每条边上的权值可以取1~t的任意正整数。
现在，Answer想要求出在给M,K,序列A和每个大节点的区间[l_i , r_i ]的情况下，有多少张不同的“图中图”，由于方案数可能很大，你只需要输出方案数模P后的答案。
*对于大节点，Answer只关心边的情况，而不关心点的情况，每个大节点中的边是有标号的，两个方案不同当且仅当，M个大节点的连接状况不同或者至少其中有一个大节点的其中一条边的权值不同。

　　输出一个整数，表示方案数模P后的值。