SP21807 PFND - Path Finding In the Country

Rahat lives in a strange country. Name of the cities of this country are also strange. Instead of traditional naming, here, cities are named by number like 1, 2, 3 …..**N**. Cities are named according to their size. That is, city **1** is the smallest city, city **2** is 2 $ ^{nd} $ smallest…. city **N** is the largest city of the country. People of the country are very concerned about traffic. To avoid collision and jam, every road is one directional. Rule of visiting from one city to another are: - When visiting from a city to a **larger** city, you must have to journey through bus. - When visiting from a city to a **smaller** city, you must have to journey through train. Rahat lives in city **1**. He wants to go in city **N**. As he likes journey very much, he wants to know, in how many ways he can complete his journey. He dislikes riding on train. So he will **not** ride on train during his journey.

Input set starts with an integer (**T**

For each case, print total way Rahat can make to arrive on city **N**. As the answer can be very big, print the answer modulo 1000000007. For correct format, look at the sample output.