The two renowned MCA scientists, Khan Saab and JayB are studying the growth of an idealized (biologically unrealistic) rat population. They experiment with a newly-born pair of rats kept in a field. They observe that rats are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rats. Rats never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. They want you to help them find the number of pairs of rats at the end of some particular month to excel in their research.

At the end of the first month, the rat couple mates, but still there is only 1 pair. At the end of the second month the female produces a new pair, so now there are 2 pairs of rats in the field. At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field.

What is the number of pairs of rats at the end of some particular month?


Input and Output 

Input consists of a line containing n, the number of test cases. For each test case, a line follows with an integer k indicating the no of months 0 < k ≤ 10^5
For each test case, print a line giving the number of rat pairs at the end of k months modulo 10000001.The answer would fit in 8 bytes(long long int).


Sample Input 






Sample Output 




using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;


namespace ConsoleApplication1


    class Program


        static void Main(string[] args)


            int numberOfMonths = 20;

            Stack newBorn = new Stack();

            Stack tempNewBorn = new Stack();

            Stack matured = new Stack();

            //Pushing newly born pair


            for (int i = 0; i < numberOfMonths; i++)


                if (matured.Count != 0)


                    int tempCount = matured.Count;

                    for (int j = 0; j < tempCount; j++)





                while (newBorn.Count != 0)




                while (tempNewBorn.Count != 0)





            Console.WriteLine("Number of pairs of rats: " + (newBorn.Count + matured.Count));




This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s