Hello! I am very hard stuck with this problem form the 2024-2025 ICPC Brazil Subregional contest more specifically this.

We are given $$$N \le 10^{18}$$$ and $$$M \le 10^5$$$ pairs $$$(a_i \le 100, b_i \le 60)$$$ that we can choose any amount of time. For pair $$$i$$$ we can subtract $$$a_i$$$ form $$$N$$$ only if $$$N \% 2^{b_i} == 0$$$. Now we need to find all the different ways in which we can obtain $$$0$$$ doing these operations. (I recommend reading the statement in case I missed to specify smth.)

First it's pretty clear that we can construct a very basic dynamic programming solution that is we iterate for all numbers $$$i \le N$$$ and for each $$$i$$$ iterate over all pairs and check if $$$i \% 2^{b_j} == 0$$$ then $$$dp[i] += dp[i - a_j]$$$. This runs in $$$\mathcal{O}(N \times M)$$$.

There is also a speedup based on the fact that for a certain $$$i$$$ if there are let's say $$$cnt$$$ trailing zeros then $$$i$$$ can use all pairs with $$$b_j \le cnt$$$. So we can precompute $$$cnt[b][i]$$$ which means the number of pairs such that $$$a_j = i$$$ and have $$$b_j \le b$$$ in $$$\mathcal{O}(M \times 100)$$$ and then we can compute the answer using a generic linear recurrence based on our calculations. Overall complexity $$$\mathcal{O}((N + M) \times 100)$$$.

This is also not enough to enter our time limit. Now from our input restrictions it's pretty clear that we will need to use Matrix Exponentiation, the only problem here is that I do not see how we can do so based on the fact that we will need for each $$$i$$$ to see the number of trailing zeros. I have seen some solutions online, I did not understand how they compute the answer, so here I am asking for help.

Any similar problem(s), or hints even would be much appreciated. Thanks!