本题读入量较大，请使用较为快速的输入方式。
南夫和拉斯在下棋，游戏在一张 个点 条边的连通图上进行，且对于每个 ，都有 与 连边。
这个游戏的规则比较特殊：首先南夫会选择一些不同的点，然后在这些位置上都下白棋，然后拉斯选择其它没被白棋下过的位置放上黑棋使得每条边的两个端点均不存在一个白棋一个黑棋的情况。
因为拉斯绝顶聪明，所以他一定会快速地选择出下黑棋最多的方案，且因为游戏要求不准有人挂机，所以拉斯和南夫都要至少下一枚棋子。所以南夫想知道，有多少种不同的下棋方案使得两个人下的棋子数量之和最多，由于答案可能很大，你只需要输出其对 取模的结果即可。
