Can someone explain me the task? What do p and q mean? And why does the answer exist(what if on every step they both roll neither 1 nor m?)

From where the 675 and 44 are came from?

Looking back at this one, I believe it can be solved quickly for n < 10^18, m < 10^18, in O( log( n ) ).

tym pass

The only problem is that I don't know how the hell is 675/44 = 113636380 (mod 10^9 + 9).

Could anyone give me an example about how to magically turn 675 and 44 into 113636380?