题目背景

飞雪连天射白鹿，笑书神侠倚碧鸳。

谨纪念金庸先生。

但是这与本题没有联系。

题目描述

wgr 是 $R$ 国军队总指挥官。现在，他决定组织两个小队分别去执行两个秘密任务。

wgr 将派出 $N$ 名战士来执行这两个任务，他们的编号为 $1 \sim N$ 。由于任务无比重要，wgr 需要使派出的队伍配合绝对默契 。配合绝对默契指队伍中任何两名战士的配合都是默契的。同时，他还需要使两个队伍的战斗力差距尽可能小，队伍的战斗力定义为 $F=2^{k}$，$k$ 为队伍的人数，不允许有人剩余。

wgr 已经知道哪些战士之间的配合是默契的，但由于时间紧迫，wgr 来不及慢慢整理资料了，现在，他请你以最快的速度帮他完成资料的整理，并告诉他：

1. 一共有多少种不同的分组方案。两种方案被认为是不同的当且仅当其两支队伍战斗力差值不同。
2. 所有分组方案中，最小的战斗力差值是多少，由于这个差值可能很大，请对 $10^9+7$ 取模后再输出。
3. 有多少对战士配合默契但是不可能被分在同一小组。

注意： 特别地，由于队伍的默契程度十分重要，一支队伍 $N$ 名战士另一支队伍 $0$ 名战士也是合法的分组方案。

输入格式

第一行两个正整数 $N,M$。

接下来 $M$ 行每行两个正整数 $x,y$，表示编号为 $x$ 的战士与编号为 $y$ 的战士之间配合默契。

输出格式

输出共两行。

第一行，如果存在合法的方案，输出一行两个数，为分组方案数与最小的战斗力差值模 $10^9+7$ 的结果；如果不存在合法的分组方案，第一行输出一个数 $-1$ 即可。

第二行，输出一个整数，表示有多少对战士配合默契但是不可能被分在同一小组。

4 4
3 4
1 2
2 4
2 3

2 0
0

10 2
1 7
3 5

-1
2

提示

本题共有三个 Subtask。

• Subtask 1：共 $5$ 个测试点，一个测试点 $5$ 分，满足 $N≤30$；
• Subtask 2：共 $3$ 个测试点，一个测试点 $10$ 分，满足 $N≤300$；
• Subtask 3：共 $3$ 个测试点，一个测试点 $15$ 分，满足 $N≤2500$。

对于所有的数据，不会重复说明同一组关系，$1\le x,y\le n$ 且 $x\neq y$。此外保证 $0\le m≤n\times (n-1)/2$。

本题开启 Special Judge：

• 若你的答案第一行输出正确你可以得到该测试点 $60\%$ 的分数；
• 若你的答案第二行输出正确你可以得到该测试点 $40\%$ 的分数。

为了确保你能够得到部分分，请按格式要求输出。