Its showing time limit exceeded. Can we do it without using DP, only with recursion cause Prateek bhaiya hasn’t started DP yet.
Here's Code https://ideone.com/78vdAO
Hey! you can do this problem without using DP and its giving TLE because as mentioned in the problem your ans can be a large value so you have to take ans % 1000000007. If you don’t know why or how you should do ans % 1000000007 please do watch the number theory section of your online course.
Hope this helps you 