The footbridge, 10¹⁸ steps

RECR-P2 counted the ways to go up a footbridge of n steps with moves of 1, 2 or 3. Now the allowed moves are given in the list steps, and n can be enormous. Return the number of different sequences of moves that end exactly at the top, modulo m (the remainder after dividing by m).

ways_mod(4, [1, 2, 3], 1000)     # 7
ways_mod(10, [1, 2], 10 ** 9)    # 89
ways_mod(7, [2], 100)            # 0
ways_mod(0, [1, 2, 3], 1000)     # 1

Limits

• n is from 0 to 10¹⁸ (a 1 followed by 18 zeros). steps holds 1 to 10 different moves, each from 1 to 10. m is from 1 to about 10¹⁸.
• A loop over every step is far too slow for n = 10¹⁸. The big tests have 2 seconds each.