D. Рута воспитала любовь, но сломала судьба
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Река Разбитых сердец протекает горизонтально через страну Судьбы и делит её на северную и южную стороны.

Инженер Рут хочет построить $$$n$$$ домов вдоль реки, пронумерованных от $$$1$$$ до $$$n$$$. Все дома на северной стороне и все дома на южной стороне должны располагаться вдоль прямых линий, параллельных реке Разбитых сердец.

Будет $$$m$$$ мостов, при этом $$$i$$$-й мост соединяет дом $$$u_i$$$ и дом $$$v_i$$$ ($$$u_i \ne v_i$$$). Гарантируется, что все $$$n$$$ домов соединены этими мостами, то есть вы можете добраться от любого дома до любого другого, переходя по мостам. Также нет двух мостов, соединяющих одну и ту же пару домов.

Рут хочет знать, сколько способов существует расположить $$$n$$$ домов вдоль реки, по модулю $$$10^9+7$$$, так чтобы для запланированных $$$m$$$ мостов выполнялись следующие условия:

  • Для каждого моста два дома, которые он соединяет, находятся на противоположных сторонах реки;
  • Мосты не пересекаются, когда их изображают прямыми линиями между домами.
Возможное расположение домов при $$$n=5$$$.

Два расположения считаются различными, если выполняется хотя бы одно из следующих условий:

  • Существует дом, который в двух расположениях находится на разных сторонах;
  • Существуют два дома $$$a$$$ и $$$b$$$, которые находятся на одной стороне в обоих расположениях, но $$$a$$$ идет перед $$$b$$$ в одном расположении, а $$$b$$$ идет перед $$$a$$$ в другом.

Поскольку Рут занят мыслями о своей бывшей, которую судьба разлучила с ним, он просит вас вычислить количество способов расположить дома вдоль реки, по модулю $$$10^9+7$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$$$) — количество домов и количество мостов.

Затем следуют $$$m$$$ строк, $$$i$$$-я строка содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$, $$$u_i\ne v_i$$$) — два дома, которые соединяет $$$i$$$-й мост.

Гарантируется, что все $$$n$$$ домов соединены мостами, и нет двух мостов, соединяющих одну и ту же пару домов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество способов расположить $$$n$$$ домов вдоль реки, по модулю $$$10^9+7$$$.

Пример
Входные данные
4
2 1
1 2
3 3
1 2
1 3
2 3
5 4
1 2
1 3
3 4
3 5
4 3
1 2
1 3
1 4
Выходные данные
2
0
8
12
Примечание

В первом наборе входных данных дом $$$1$$$ должен быть построен на северной стороне, а дом $$$2$$$ на южной стороне, или наоборот.

Во втором наборе входных данных как минимум два дома должны быть построены на одной стороне реки. Но каждая пара домов соединена мостом. Таким образом, в каждом расположении как минимум один мост не пересечет реку. Следовательно, ответ равен $$$0$$$.

В третьем наборе входных данных одно из возможных расположений домов представлено в условии задачи.