Malnar 先生放弃了他对树的执念，转而发现了更有趣的东西：仙人掌图！形式化地讲，仙人掌图是一个连通图，其中每条边最多包含在一个环中。环被定义为一个由多于一条不同的边组成的序列，其中每两条相邻的边共享一个公共端点，且第一条边和最后一条边也共享一个公共端点。

不幸的是，Malnar 先生买到的仙人掌图太大了，所以他想把它切割成不相交的“棍子”。一根“棍子”被定义为一对共享公共端点的边。Malnar 先生是一个严谨的人，他想知道将他的仙人掌图切割成棍子的方案总数。

输入格式

第一行包含顶点数 $N$ 和边数 $M$。接下来 $M$ 行，每行包含两个不同的整数 $A_i$ 和 $B_i$，表示顶点 $A_i$ 和 $B_i$ 之间的一条边。每条边仅会被列出一次。

数据范围

• $1 \le N, M \le 100\,000$
• $1 \le A_i, B_i \le N$

输出格式

计算 Malnar 先生将他的仙人掌图切割成棍子的不同方案数。由于这个数字可能非常大，请输出结果对 $10^6 + 3$ 取模后的值。

样例

输入 1

10 12
1 6
2 5
7 2
8 9
8 1
2 6
4 3
4 10
3 10
3 9
1 3
5 7

输出 1

8