Связный неориентированный граф называется вершинным кактусом, если каждая вершина этого графа принадлежит не более чем одному простому циклу.
Простым циклом в неориентированном графе назовем последовательность различных вершин v1, v2, ..., vt (t > 2) такую, что для любого i (1 ≤ i < t) существует ребро между вершинами vi и vi + 1, а также существует ребро между вершинами v1 и vt.
Простым путем в неориентированном графе назовем последовательность не обязательно различных вершин v1, v2, ..., vt (t > 0) такую, что для любого i (1 ≤ i < t) существует ребро между вершинами vi и vi + 1, причем каждое ребро встречается не более одного раза. Будем говорить, что простой путь v1, v2, ..., vt начинается в вершине v1 и заканчивается в вершине vt.
Вам задан граф, состоящий из n вершин и m ребер, который является вершинным кактусом. Также есть список из k пар интересных вершин xi, yi, для которых Вы захотели узнать следующую информацию — сколько различных простых путей начинается в вершине xi и заканчивается в вершине yi. Два простых пути будем считать различными, если различаются множества ребер, которые в них входят.
Для каждой пары интересных вершин посчитайте количество различных простых путей между ними. Поскольку это количество может быть достаточно большим, требуется посчитать остаток от деления этого числа на 1000000007 (109 + 7).
Выходные данные
Выведите k строк: в i-ой строке выведите единственное число — остаток от деления количества различных простых путей, начинающихся в xi и заканчивающихся в yi, на 1000000007 (109 + 7).