Consider a path of the form (0,0) -> (p,b) -> (p, b+1) -> (n,m)
This is present in (0,0) -> (p,b) -> (n,m) and also (0,0) -> (p+1,b) -> (n,m)
So it will be counted in p as well as p+1.
Thus it leads to over counting.
result should be positive
got it right! just had to do result%MOD in every iteration of loop.
http://www.codechef.com/viewsolution/1628252
In calculating inverse for integer(suppose for example 800000) we need to calculate A^(MOD-2). In the power function there is a step in which we have to calculate A * A(which equals 6.4*10^11 for above example). So, we can calculate only up to inverse such that A * A is in range for data type.
You are correct. It is fixed.
@betlista you are saying that (0,0)->(p,b-1)->(p,b)->(n,m) will occurs twice in the case of (p,b-1) and again for (p,b).But this will happen with (p,b-1) also.It will also occurs twice one for (p,b-2) and for (p,b-1) in this way again we are over counting. Am i right??
because the range of N+M is upto 800000 …
and n+m are the number of steps which ant has to move
correct me if i m wrong…
I didn’t know that there was another method other than power and extended euclidean for finding modular inverse. Thank you.