Bytelon 村的居民决定利用自然能源为他们的房屋供电，因此他们决定建造许多风车。

Bytelon 的所有住户都位于道路的一侧（Bytelon 只有一条路），呈直线排列；所有的风车也建造在道路的另一侧，同样呈直线排列。一些风车与一些住户之间通过横跨道路的高压线相连。

一个风车可以连接多个住户，一个住户也可以连接多个风车。同样，有些风车或住户可能根本没有连接。每条连接线都是一条直线。对于任何一对风车和住户，至多只有一条高压线。

然而，Bytelon 政府并不喜欢这种方案。他们认为，当每个风车至多为一个住户供电，且每个住户至多由一个风车供电时，效率会更高。此外，高压线不应在地面上的同一点交叉。换句话说，从鸟瞰图观察这些高压线（所有高压线都被视为直线）时，它们不应相交。这些条件是由强风引起的，否则强风可能会将高压线推向彼此，导致短路。

Bytelon 政府要求你编写一个程序，计算选择部分高压线的方法总数，使得所选线路集合满足上述要求。

政府不喜欢处理大数字；你的程序只需计算方案总数除以政府指定数字后的余数。

编写一个程序，完成以下任务：

• 从标准输入读取已建高压线的描述；
• 确定方案总数除以指定数字后的余数；
• 将结果写入标准输出。

输入格式

输入的第一行包含四个整数 $n$、$m$、$k$ 和 $r$（$1 \le n, m \le 200\,000$，$1 \le k \le 1\,000\,000$，$2 \le r \le 10^{9}$），用空格分隔，分别代表：住户数量、风车数量、高压线数量以及政府给定的数字。住户编号为 $1$ 到 $n$，风车编号为 $1$ 到 $m$。住户沿道路按 $1$ 到 $n$ 的顺序排列。在道路的另一侧，风车按 $1$ 到 $m$ 的顺序排列。

接下来的 $k$ 行中，第 $i$ 行包含两个整数 $h_{i}$ 和 $w_{i}$（$1 \le h_{i} \le n$，$1 \le w_{i} \le m$，对于 $1 \le i \le k$），用空格分隔，表示连接第 $h_{i}$ 个住户和第 $w_{i}$ 个风车的第 $i$ 条高压线。

输出格式

第一行且仅包含一个整数，表示连接住户与风车的合法方案总数除以 $r$ 后的余数。

样例

输入 1

3 3 5 100
1 2
2 3
3 1
2 1
3 2

输出 1

8

存在一种不选择任何高压线的方案（虽然这种方案在实践中似乎没有意义，但它符合规则……），有 5 种选择仅一条线路的方案，2 种选择两条线路的方案，没有选择三条线路的方案。