I am getting wrong answer . The code is at http://www.codechef.com/viewsolution/4479206.
Kindly help me find the mistake.
Thank you 
Minor mistake.
http://www.codechef.com/viewsolution/4479806
Here’s the link to your AC solution. Note that problem statement says that you have to output final answer modulo 10000009.