哈里波特在霍格沃茨魔法学校迎来了第一堂魔药课。
霍拉斯·斯拉格霍恩老师，给每位同学发放了 N 种不同的魔药，编号 1 \sim N，他希望同学们学会配置高魔力值的药水。
老师告诉大家，这 N 种魔药中，有 M 对魔药，两两相克，神奇的是，如果将这些两两相克的魔药倒在一起，反而会提升配置出来药水的魔力值。
具体来说，老师先给大家一个魔法药瓶，这个魔法药瓶的初始魔力值为 1，同学们依次倒入 N 种药水，如果向药瓶中倒入第 i 种药水时，这种药水和瓶子中的某种或某几种药水相克，那么此时魔法药瓶中药水的魔力值会立刻翻倍（\times 2）。
现给出 M 种两两相克的药水数据，请计算出，哈里波特能够配置出药水的最大魔力值是多少？
第 1 行读入两个整数 N,M。
接下来 M 行，每行读入两个整数 X,Y 表示一对相克的魔药编号。（同一对相克的魔药仅会被读入一次）
请输出哈里波特配置出魔药的最大魔力值，这个值可能会很大，如果该值大于 1018，你只需要输出该值 mod 1018 的结果。（mod 表示求余数）
6 3 1 2 3 4 5 6
8
8 4 1 2 2 3 3 4 5 6
16
有 6 种魔药，其中有 3 种两两相克。
倒入魔药 1 魔力值为 1。
倒入魔药 2 魔力值为 1 \times 2 = 2。
倒入魔药 3 魔力值为 2。
倒入魔药 4 魔力值为 2 \times 2 = 4。
倒入魔药 5 魔力值为 4。
倒入魔药 6 魔力值为 4 \times 2 = 8。
对于 30\% 的数据，1 \le N \le 10，1 \le M \le 50。
对于 100\% 的数据， N \le 1000，X \neq Y，1 \le X,Y \le N，1 \le M \le 5000。
东方博宜OJ