I tried to solve the problem using the hockey stick pattern in the pascal triangle…and came to conclusion that
final answer will be of form (nCr -1)mod m…i know that (nCr)mod m can be calculated by lucas method ,but i am really confused how to calculate (nCr -1)mod m…pls help me thank you!
You can read about different ways of computing nCr mod p: Lucas | COME ON CODE ON
For a clear (I believe) implementation of Lucas’ theorem you can check my implementation: source
though nCr mod p can be computed by the methods you described,my real confusion was how to tackle “-1” in the real problem…
as (nCr-1)mod p is not equal to nCr mod p - 1.
Well (-1) % 10 == (-1 + 10) % 10 = 9.
So you can print : ((nCr % MOD) - 1 + MOD) % MOD