T448342 P2194仿制版 ZYK烧男娘

众所不周知，ZYK已经加入了 SNN 团。现在他（她）要开始喜（sang）闻（xin）乐（bing）见（kuang）地烧男娘了。 他（她）所在的学校有 n 座宿舍楼， n 个男娘分别在每座宿舍楼里，然后宿舍楼里都有白磷，但是要使用它需要抄一些书。 m 条单向通道连接相邻的两个男娘所在宿舍楼。 ZYK有个绝技，如果他（她）（用括号的原因懂的都懂）能从一个点开始烧，最后回到这个点，那么烧这条回路上的男娘的费用只需要抄该点的书即可。并且每只男娘只需烧一遍，宿舍楼可以重复去。然后他（她）想花抄尽可能少的书烧掉所有的男娘。 问：最少需要抄多少书，并且当抄书最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对10的9次方+7的取模结果。 （注：这里ZYK每次可以从任何一个点开始走回路。就是说一个回路走完了，下一个开始位置可以任选。所以说不存在烧不了所有男娘的情况，即使图不连通，ZYK自行选择顶点进行烧男娘行动。且走过的道路可以重复走。）

第一行一个正整数 n。 第二行 n 个正整数，表示每个点的抄书数 w i 。 第三行一个正整数 m。 接下来 m 行，每行两个正整数 x i ,y i ，表示一条 x i →y i 的单向道路。

输出一行两个整数，分别表示最小花费，和花费最小时的方案数。

对于30% 的数据，1