时间限制： 1.0 秒

空间限制： 512 MB

题目描述

小 H 为了完成一篇论文，一共要完成 $n$ 个实验，其中第 $i$ 个实验需要 $a_i$ 的时间去完成。

小 H 可以同时进行若干实验，但存在一些实验，只有当它的若干前置实验完成时，才能开始进行该实验。

同时我们认为小 H 在一个实验的前置实验都完成时，就能马上开始该实验。

为了让小 H 尽快完成论文，需要知道在最优的情况下，最后一个完成的实验什么时候完成？

小 H 还想知道，在保证最后一个实验尽快完成的情况下（即保证上一问的答案不变），他想知道每个实验最晚可以什么时候开始。

设第 $i$ 个实验最早可能的开始时间为 $f_i$，不影响最后一个实验完成时间的最晚开始时间为 $g_i$，请你回答 $\prod\limits ^n_{i = 1}(g_i − f_i + 1)$ 除以 $10^9 + 7$ 所得的余数。

题目保证有解。

输入格式

从标准输入读入数据。

第一行输入一个整数 ${n, m}$。

第二行输入 $n$ 个正整数，$a_1, a_2, \cdots a_n$，描述每个实验完成所需要的时间。

接下来读入 $m$ 行，每行读入两个整数 $u, v$，表示编号为 $u$ 的实验是编号为 $v$ 的实验的前置实验。

对于所有的输入数据，都满足 $1 \le n \le 10^5,~1 \le m \le 5 \times 10^5,~1 \le a_i \le 10^6$。

输出格式

输出到标准输出。

第一行输出一个整数表示最晚完成的实验的时间。

第二行输出一个整数表示 $\prod\limits^n_{i = 1}(g_i − f_i + 1)$ 除以 $10^9 + 7$ 所得的余数。

7 5
11 20 17 10 11 17 17
5 4
6 1
7 3
2 4
2 1

34
7840

样例 1 解释

第一个实验最早开始时间为 $20$，最晚开始时间为 $23$。

第二个实验最早开始时间为 $0$，最晚开始时间为 $3$。

第三个实验最早开始时间为 $17$，最晚开始时间为 $17$。

第四个实验最早开始时间为 $20$，最晚开始时间为 $24$。

第五个实验最早开始时间为 $0$，最晚开始时间为 $13$。

第六个实验最早开始时间为 $0$，最晚开始时间为 $6$。

第七个实验最早开始时间为 $0$，最晚开始时间为 $0$。

$ans = (23 - 20 + 1) \times (3 - 0 + 1) \times (17 - 17 + 1) \times (24 - 20 + 1) \times (13 - 0 + 1) \times (6 - 0 + 1) \times (0 - 0 + 1) \equiv 7840 \pmod {10^ 9 + 7}$。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。