如果一个有向图中存在从 $u$ 到 $v$ 的路径，且存在从 $v$ 到 $u$ 的路径，则称顶点 $u$ 和 $v$ 是强连通的。注意，如果 $u$ 和 $v$ 强连通，且 $v$ 和 $w$ 强连通，那么 $u$ 和 $w$ 也强连通。因此，图的顶点被划分为若干个集合——强连通分量。属于同一个强连通分量的顶点与该分量内的所有顶点（包括自身）强连通，且与分量外的任何顶点都不强连通。

在图论课上，Alice 在黑板上画了一个有 $n$ 个顶点的有向图，并标出了它的强连通分量。课间休息时，Bob 决定捉弄一下 Alice，擦掉了图中一些边的方向。他希望 Alice 能根据剩余的边以及休息后强连通分量的划分，唯一地恢复出被擦掉的方向。

请帮助 Bob 确定他最多可以擦掉图中多少条边的方向，以及他有多少种方法可以做到这一点。

更正式地说，找到一个边子集 $A$ 的最大大小，使其满足以下性质：如果擦掉集合 $A$ 中边的方向，那么根据关于旧强连通分量的信息以及不在集合 $A$ 中的边的方向，集合 $A$ 中边的方向可以被唯一地恢复，且强连通分量保持不变。

由于此类最大子集的数量可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

能够正确确定集合 $A$ 的最大大小，但无法正确给出此类子集数量的解法将获得部分分数。

输入格式

第一行包含三个整数 $n, m$ 和 $g$ ($2 \le n \le 2000, 1 \le m \le 2000, 0 \le g \le 7$)，分别表示图中的顶点数、边数以及测试组号。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示第 $i$ 条边的起点和终点。

保证对于任意 $1 \le i, j \le n$，$(u_i, v_i) \neq (u_j, v_j)$ 且 $(u_i, v_i) \neq (v_j, u_j)$，这意味着任意两个顶点之间最多只有一条边，不考虑方向。

输出格式

第一行输出一个数字，表示可以擦掉方向的边的最大子集的大小。

第二行输出一个数字，表示此类子集的数量对 $10^9 + 7$ 取模的结果。如果你不想提供此类子集的数量，则在第二行输出一个 $1$ 到 $10^9 + 6$ 之间的任意数字。在这种情况下，你的解法将获得该测试点的部分分数。

注意，如果在第二行省略任何数字，将导致该测试点被判为“Wrong Answer”并获得零分，无论子集大小是否正确。

样例

样例输入 1

5 6 0
1 2
1 5
2 3
3 4
3 5
4 2

样例输出 1

3
3

说明

样例中图的强连通分量高亮显示如下：

虚线边的方向可以被移除。事实上，边 $(1, 5)$ 不能被反向，否则顶点 $1, 2, 3$ 和 $5$ 将属于同一个强连通分量。边 $(3, 4)$ 和 $(4, 2)$ 也不能被改变方向，否则顶点 $2, 3$ 和 $4$ 将不再属于同一个强连通分量。

现在，考虑一种选择边子集的错误方式：

这里，粗虚线边的方向不能被移除。例如，如果我们反转边 $(1, 2)$ 和 $(1, 5)$ 的方向，我们得到的图具有相同的强连通分量分解。

可以证明，恰好有 $4$ 条边的方向不能被移除，因此答案是 $3$。

子任务