Description

nswer在看过碟中谍后，对“X中X”很感兴趣，于是想探究“图中图”。 “图中图”的外图是一张由M个大节点组成的有K条边(无重边和自环)的无向无权图(不一定连通)，外图中的每个大节点的内部又是一张由若干条边组成的无向有权图。 Answer想要构一张“图中图”，对大节点之间的边可以随便连K条，对每个大节点内部的无向图，Answer有一种生成方法：

1. 先确定一个长度为N的序列A
2. 对于每个大节点，确定一个在A中的区间[l ~i ~ , r ~i~ ]
3. 那么在第i个大节点中， 边数=sigma(sum ~x~ +num~x~ ^3^ ) 区间[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个大节点的连接状况不同或者至少其中有一个大节点的其中一条边的权值不同。

Format

Input

输入的第一行包含四个正整数N,M,P,K。 第二行包含N个正整数A ~i~ 。 以下M行，每行包含两个正整数l ~i~ ,r ~i~ 。 意义如上。

Output

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

Samples

5 3 22 2
1 2 1 3 1
1 3
2 4
3 5

14

Limitation

样例说明

外图中有3个大节点，那么连2条边，有3种连法

第一个大节点中有11条边，每条边可以取值1~2

第二个大节点中有6条边，每条边可以取值1~3

第三个大节点中有11条边，每条边可以取值1~2

所以总方案数模22得14

数据规模和约定

设P=p1 c1 *p2c2 *…*ptct ，pi为质数。

对于30%的数据，满足N,M≤1000,M2<P<10^9且P是质数

另有20%的数据，满足N,M≤1000

对于100%的数据,满足N,M≤50000 , K≤M*(M-1)/2 , 0≤ai≤10^9

pi^ci ≤100000 , P≤10^9