I am using matrix exponential for this ques but it is not working for N>=1000 as time complexity for matrix expo is N^3logT hence TLE is coming can u please suggest how to deal with this kind of question
MY CODE FOR MATRIX EXPO APPROACH =>https://ide.codingblocks.com/s/243873
@gagangoyal674
You rightly pointed out
And as you might have guessed this question is not based on matrix exponentiation completely
To solve for N>=1000 you need another concept
Have a look at this
https://github.com/tr0j4n034/SPOJ/blob/master/SUMSUMS.cpp
how are they computing 1/(n+1) in this by power(n,mod-2)
@gagangoyal674
Inverse modulo of N with respect to a prime P can be calculated by taking pow(N,P-2)
See method 3