보스의 강도 낮추기

열성 게이머 Fulano는 온라인 게임 "Boss Challenge"에서 어려운 도전 과제를 만났다. 목표는 고대 룬 문자로 강도가 표시된 강력한 보스를 쓰러뜨리는 것이다. 룬 문자는 거대한 이진수 $N$을 나타내며, 이 수가 적의 전체 강도다.

보스를 쓰러뜨리기 위해 Fulano에게는 $M$가지 서로 다른 주문이 있다. 목표는 이 주문들을 사용해 적의 전체 강도를 0까지 줄이는 것이다. $i$번째 주문은 두 정수 $a_i$와 $b_i$로 주어진다. 주문을 사용하면 $N$의 값이 $a_i$만큼 줄어든다. 주문은 두 조건을 모두 만족하는 동안 원하는 만큼 몇 번이고 쓸 수 있다.

• $a_i$는 $N$의 현재 값보다 작거나 같아야 한다.
• $N$의 현재 값은 $2^{b_i}$로 나누어떨어져야 한다. 즉, $N$의 마지막 $b_i$자리가 모두 0일 때만 주문 $i$를 쓸 수 있다.

Fulano는 주문을 조합해 이진수 $N$을 정확히 0으로 만드는 방법이 몇 가지인지 알고 싶어 한다. 주문을 사용하는 순서가 다르면 서로 다른 조합으로 본다.

조합의 수가 매우 클 수 있으므로, 답은 $10^9 + 7$로 나눈 나머지로 출력한다.

Fulano가 답을 찾도록 도와주자.

첫 번째 줄에 보스의 강도를 나타내는 정수 $N$ ($1 \le N \le 10^{18}$)이 주어진다.

두 번째 줄에 주문의 개수 $M$ ($1 \le M \le 10^5$)이 주어진다.

이어지는 $M$개의 줄에는 각각 두 정수 $a_i$ ($1 \le a_i \le 100$)와 $b_i$ ($0 \le b_i \le 60$)가 주어진다.

주문을 사용해 보스의 강도를 $N$에서 $0$으로 줄이는 서로 다른 순서의 개수를 $10^9 + 7$로 나눈 나머지로 출력한다.