We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
As there involves many large numbers in each test case, so applying the formula C ( m+n-2, m-1) or C (m+n-2, n-1) directly will not work.
We have to use a bit of number theory here.
To find the factorial of a number, n!, instead from 1 to n, we also have to mod put the value at each step of multiplication so that the multiplication becomes fast.
According to fermat's little theorem,
a ** ( p - 1 ) == 1 mod( p )
==> ( a ** ( p - 1 ) ) * ( a ** ( -1 )) == a ** ( -1 ) mod( p )
Matrix Tracing
You are viewing a single comment's thread. Return to all comments →
As there involves many large numbers in each test case, so applying the formula C ( m+n-2, m-1) or C (m+n-2, n-1) directly will not work.
We have to use a bit of number theory here.
To find the factorial of a number, n!, instead from 1 to n, we also have to mod put the value at each step of multiplication so that the multiplication becomes fast.
According to fermat's little theorem, a ** ( p - 1 ) == 1 mod( p )
==> ( a ** ( p - 1 ) ) * ( a ** ( -1 )) == a ** ( -1 ) mod( p )
==> a ** ( p - 1 - 1 ) == a ** ( -1 ) mod( p )
==> a ** ( p - 2 ) == a ** ( -1 ) mod( p )
==> a ** ( -1 ) == a ** ( p - 2 ) mod( p )