Desafio do Chefão

Fulano, um jogador ávido, se deparou com um desafio épico no jogo online “Desafio do Chefão”. O objetivo é derrotar um chefão poderoso, cujo poder é descrito por um conjunto de runas ancestrais. Essas runas representam um número binário gigante $N$ , indicando a força total do inimigo. Para vencer o chefão, Fulano dispõe de $M$ magias diferentes, e o objetivo é reduzir a força total do inimigo a zero utilizando essas magias. A i-ésima magia está associada a dois inteiros $a_i$ e $b_i$ . Ao ser lançada, a magia $i$ reduz o valor de $N$ em $a_i$ unidades. Tal magia pode ser lançada quantas vezes o jogador quiser, desde que duas condições especı́ficas sejam atendidas:

• O valor de $a_i$ deve ser menor ou igual ao valor atual de $N$.

• O valor atual de $N$ deve ser divisı́vel por $2^{b_i}$. Em outras palavras, a magia $i$ só pode ser utilizada se os últimos $b_i$ dı́gitos de $N$ forem zeros.

Fulano está fascinado pelo jogo e quer descobrir de quantas maneiras diferentes ele pode combinar as magias para reduzir o número binário $N$ a exatamente zero e, assim, derrotar o chefão. Duas combinações são consideradas diferentes se a sequência em que as magias são lançadas for diferente. Como o número de combinações possı́veis pode ser muito grande, a resposta deve ser dada módulo $10^9 + 7$.

Ajude Fulano a encontrar a resposta!

A primeira linha contém um único número inteiro $N$ $(1 ≤ N ≤ 10^18 )$, representando o poder do chefão.

A segunda linha contém um único número inteiro $M$ $(1 ≤ M ≤ 10^5 )$, denotando o número de magias disponı́veis.

As próximas $M$ linhas contêm as descrições das magias: a i-ésima destas linhas contém dois números $a_i$ $(1 ≤ a_i ≤ 100)$ e $b_i$ $(0 ≤ b_i ≤ 60)$.

Imprima um único número inteiro: o número de sequências de usos de magias admissı́veis (tomados módulo $10^9 + 7$), que reduzem o poder do chefão de $N$ para 0.