该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

有几个模块需要依次通电调试。有的模块必须先检查，有的模块后检查；相邻两次调试的功耗变化也不能太大。学长想知道：“这些模块到底有多少种合法的调试顺序？”

题目描述

共有 n 个模块，编号为 1 到 n，第 i 个模块的功耗为 p_i。一次完整调试需要将每个模块恰好调试一次，因此调试顺序是这 n 个编号的一个排列。

合法的顺序必须同时满足：

1. 给出的每条先后关系 (u,v) 都得到满足，即 u 号模块必须在 v 号模块之前调试。这里要求的是先后顺序，不要求两者相邻。
2. 对于调试顺序中任意两个相邻模块，其功耗差的绝对值不超过 D。

不同编号的模块即使功耗相同，也视为不同模块。请计算合法调试顺序的数量。如果不存在合法顺序，输出 0。

输入格式

第一行输入三个整数 n、m、D，分别表示模块数量、先后关系数量和允许的最大相邻功耗差。

第二行输入 n 个整数，依次表示 1 到 n 号模块的功耗。

接下来 m 行，每行输入两个整数 u、v，表示 u 号模块必须在 v 号模块之前调试。

输出格式

输出一个整数，表示合法调试顺序的数量。

样例

4 1 3
2 5 3 6
1 4

6

样例解释

1 号模块必须在 4 号模块之前。两者功耗差为 4，超过 D，因此不能相邻。满足条件的顺序共有 6 个，包括 1 2 3 4、1 2 4 3 等。

数据范围与限制

• 2 ≤ n ≤ 8；
• 0 ≤ m ≤ n(n-1)；
• 0 ≤ D ≤ 100，1 ≤ p_i ≤ 100；
• 1 ≤ u,v ≤ n，u ≠ v，各条关系互不相同；
• 先后关系可能互相矛盾，此时没有合法顺序；
• 时间限制：1 秒；内存限制：256 MiB。