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).
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));