Decrease the Boss Strength

Fulano, an avid gamer, has come across an epic challenge in the online game "Boss Challenge". The goal is to defeat a powerful boss, whose power is described by a set of ancient runes. These runes represent a giant binary number $N$, which is the total strength of the enemy.

To defeat the boss, Fulano has $M$ different spells at his disposal. The goal is to reduce the total strength of the enemy to zero using these spells. The $i$-th spell is described by two integers $a_i$ and $b_i$. When used, the $i$-th spell reduces the value of $N$ by $a_i$. A spell can be used as many times as the player wants, as long as two conditions hold:

• The value of $a_i$ is less than or equal to the current value of $N$.
• The current value of $N$ is divisible by $2^{b_i}$. In other words, spell $i$ can only be used if the last $b_i$ binary digits of $N$ are zeros.

Fulano wants to know how many different ways he can combine the spells to reduce the binary number $N$ to exactly zero. Two combinations are considered different if the order in which the spells are used is different.

The number of combinations can be very large, so the answer should be printed modulo $10^9 + 7$.

Help Fulano find the answer.

The first line contains a single integer $N$ ($1 \le N \le 10^{18}$), the power of the boss.

The second line contains a single integer $M$ ($1 \le M \le 10^5$), the number of spells.

Each of the next $M$ lines contains two integers $a_i$ ($1 \le a_i \le 100$) and $b_i$ ($0 \le b_i \le 60$).

Print the number of different sequences of spell uses that reduce the power of the boss from $N$ to $0$, modulo $10^9 + 7$.