题目描述

给定一张包含 $N$ 个顶点的无向简单图，顶点编号为 $0,1,\ldots,N-1$。一次游行需要连续经过恰好五条街道，并且这五条边必须两两不同。游行过程中允许多次经过同一个顶点。也就是说，我们要统计所有长度为 $5$ 的有向边序列，其中五条无向边互不相同。行走顺序不同视为不同游行方案。

图由伪随机过程生成。令 state=seed，按照 $x=0,1,\ldots,N-1$，以及 $y=x+1,x+2,\ldots,N-1$ 的顺序枚举所有点对，每次执行：

state = (state * 1103515245 + 12345) mod 2^31。

如果新的 state < threshold，就加入无向边 $(x,y)$。

随后给出一个偶数长度数组 toggle。对每一对 toggle[2i], toggle[2i+1]：如果对应边当前存在就删除，否则就加入。

求最终图中不同游行方案的数量。答案保证可以用 64 位有符号整数表示。

输入格式

第一行四个整数 L N seed threshold，其中 $L$ 是数组 toggle 的长度。

如果 $L>0$，第二行包含 $L$ 个整数，依次为 toggle[0], toggle[1], ..., toggle[L-1]。如果 $L=0$，没有第二行数据。

输出格式

输出一个整数，表示不同游行方案的数量。

数据范围

• $1\le N\le500$；
• $0\le seed<2^{31}$；
• $0\le threshold<2^{31}$；
• $0\le L\le200$，且 $L$ 为偶数；
• 每个 toggle 元素均在 $[0,N-1]$ 内；
• 对每个 $i$，toggle[2i] < toggle[2i+1]。

样例 1

10 10 47 0
0 1 1 7 2 7 3 4 2 3

2

样例 2

0 4 47 2147483647

72