Given two no. A and S, there are coins with values A,A+1,A+2,…,S. Find the no. of ways in which we can make the some A using the values of coin specified above. Since answer can be big it should be modulo with 10^{9}+9.

This is link to my solution, I am getting run time error (RTE) in one test case. anyone please help me out.