У Валеры есть $$$n$$$ кроликов, пронумерованных от $$$1$$$ до $$$n$$$. Так как их численность быстро растет, он хочет разделить их на две группы: группа номер $$$0$$$ и группа номер $$$1$$$. Обозначим $$$f(x) = y$$$ — кролик с номером $$$x$$$ относится к группе номер $$$y$$$. Например, $$$f(3) = 1$$$ означает, что кролик с номером $$$3$$$ относится к группе номер $$$1$$$. Тогда, если есть два кролика с номерами $$$a$$$ и $$$b$$$, такими, что $$$a$$$ делится на $$$b$$$, то должно выполняться следующее условие: $$$f(a) = f(b)\ OR\ f(\frac{a}{b})$$$, где $$$OR$$$ — операция побитового "ИЛИ". Невыполнение этого условия приведет к войне между двумя группами. Для $$$m$$$ кроликов Валера уже определил группу, к которой будет относиться каждый из них, однако дальше он просит вашей помощи. Помогите ему найти количество способов разделить кроликов на две группы так, чтобы они не начали войну, а кролики, для которых Валера определил группу, были в соответствующих группах. Так как это число может быть достаточно большим, Валеру интересует остаток от деления этого числа на $$$10^9+7$$$.
В первой строке содержатся два целых числа, разделенных пробелами $$$n$$$ и $$$m$$$ — общее количество кроликов и количество кроликов, для которых Валера уже определил группу, соответственно.
В следующих $$$m$$$ строках содержатся по два целых числа $$$x_i$$$ и $$$y_i$$$. Каждая из этих строк означает, что кролик с номером $$$x_i$$$ должен находиться в группе номер $$$y_i$$$. Гарантируется, что все $$$x_i$$$ различны.
$$$$$$1 \le n \le 10^6$$$$$$ $$$$$$1 \le m \le 18$$$$$$ $$$$$$1 \le x_i \le n$$$$$$ $$$$$$0 \le y_i \le 1$$$$$$
В единственной строке выведите одно число — количество способов разбить кроликов на две группы, которые удовлетворяют заданным условиям, по модулю $$$10^9+7$$$.
5 2 4 1 2 0
0
5 2 2 1 3 1
3
| Name |
|---|


