Two Tables

Mouse Stofl is going to host an «End of the World»-after party in December. As he likes to plan ahead he already wants to decide who will sit at which table during the main course. Stofl has two large tables, each of which can seat an arbitrary amount of people. The only problem is that some people don't mix very well and are bound to argue if they sit at the same table. As an example Richard doesn't like Bill very much and Steve doesn't like Richard, so Richard must be seated away from the other two (luckily for Stofl they don't mind each other). Stofl has a long list of such incompatibilities and would like to know in how many different ways he can seat his guests without there being any argueing.


Write a program to determine the amount of possibilities for Stofl to distribute his guests, given the list of incompatible guests (numbered for anonymity).


The first line contains two integers $n$ and $m$, the number of guests and the number of conflicts. The following $m$ lines contain two integers $a$ and $b$ ($a < b$) indicating that guest $a$ isn't allowed to sit at the same table as guest $b$. Any pair $a,b$ doesn't appear more than once.


One line containing the number of possible ways to seat the guests. As the number of possibilities can get really big, we are only interested in the last 100 digits of the result (so only print those).


  • For testcases worth 40% of the points, it holds that $1 \le n \le 12$.
  • For testcases worth 60% of the points, it holds that $1 \le n \le 30$.
  • For testcases worth 80% of the points, it holds that $1 \le n \le 1\,000$.
  • For testcases worth 100% of the points, it holds that $1 \le n \le 200\,000$ and $0 \le m \le 1\,000\,000$.

Example 1


4 4
1 2
2 3
3 4
1 4


Example 2


5 1
1 5


Example 3


3 3
1 2
2 3
1 3