在远古魔法世界中，有 块蕴含强大力量的魔法水晶，第 块水晶的激活需要消耗魔力 。 这些水晶之间由 条单向传送门相连，第 条传送门可将咒术师从水晶 传送到水晶 。 咒术师掌握了“回路铭刻”术： 若他在某块水晶 处开启铭刻，并沿着传送门行进，最终能回到 ，那么经过的所有水晶都可一次性被铭刻，仅需消耗起点水晶的激活魔力 ； 咒术师可多次从任意水晶发起回路，直至所有水晶均被铭刻。 请帮助咒术师： 在完成全部水晶铭刻的前提下，将总消耗魔力最小化； 若存在多种消耗相同的最优铭刻方案，计算方案总数，并对 取模。 【名词解释】 回路：回路 指沿传送门方向行走，最终回到起点的路径，可重复经过同一水晶或传送门。 铭刻方案：方案 指一系列回路操作，使得每块水晶至少在某次回路中出现过一次。

输入描述:

第一行输入整数 ，表示水晶数量； 第二行输入 个整数 ，依次表示每块水晶的激活魔力； 第三行输入整数 ，表示传送门数量； 接下来 行，每行输入两个整数 ，表示存在一条从水晶 指向水晶 的单向传送门。

输出描述:

输出一行，包含两个整数： 所需的最小总消耗魔力； 在该最小消耗下的可行铭刻方案数对 取模后的结果。