#9341. 「USACO12JAN」 Bovine Alliance G 提高+/省选−

贝茜和她附近农场的奶牛朋友们最终决定，她们要修一些道路将她们的农场连接起来，努力组成一个联盟来对付农民。

共有 个农场，最开始计划每个农场修建一条通往另一个农场的道路，也就是说一共修建 条道路。

然而，在项目实施了几个月后，只有 条道路被真正修建完成。

现在，农场之间发生了激烈的争吵，主要的争议点在于这 条道路究竟是哪些农场修建完成的。

争论影响着联盟的和睦，为了缓和紧张的局势，贝茜希望计算出共有多少种修建出这 条道路的不同可能性。

例如，如果存在一条连接农场 和农场 的道路，一种可能性是该道路由农场 的牛修建完成，另一种可能性是该道路由农场 的牛修建完成。

如果两个关于修建道路归属的合理推测中至少存在一条道路被认为是由不同农场修建完成的，那么这两个推测被认为是不同的。

请输出所有关于修建道路归属的合理推测的总数量对 取模后的结果。

第 行：两个整数 和 。

第 行：第 行描述第 条道路，每行包含两个整数 和 ，表示农场 和农场 之间存在一条道路。

输出所有关于修建道路归属的合理推测的总数量对 取模后的结果。

如果不存在满足条件的合理推测，则输出 。

样例输入

5 4
1 2
3 2
4 5
4 5

样例输出

6

样例解释

共有 种关于修建道路归属的合理推测。

用 表示农场 修建了道路 ，农场 修建了道路 ，农场 修建了道路 ，农场 修建了道路 。

所有合理推测如下：

{2, 3, 4, 5}
{2, 3, 5, 4}
{1, 3, 4, 5}
{1, 3, 5, 4}
{1, 2, 4, 5}
{1, 2, 5, 4}

,
,
,