Река Разбитых сердец протекает горизонтально через страну Судьбы и делит её на северную и южную стороны.
Инженер Рут хочет построить $$$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$$$.
42 11 23 31 21 32 35 41 21 33 43 54 31 21 31 4
2 0 8 12
В первом наборе входных данных дом $$$1$$$ должен быть построен на северной стороне, а дом $$$2$$$ на южной стороне, или наоборот.
Во втором наборе входных данных как минимум два дома должны быть построены на одной стороне реки. Но каждая пара домов соединена мостом. Таким образом, в каждом расположении как минимум один мост не пересечет реку. Следовательно, ответ равен $$$0$$$.
В третьем наборе входных данных одно из возможных расположений домов представлено в условии задачи.
