Migrated from Lutece 1282 被兵暴的沈宝宝

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

沈宝宝：“哎，又是平常稀疏而又无聊的一天啊。”

众所周知，沈宝宝打SC2已经到了炉火纯青的地步，是难逢敌手，也独孤求败。

进攻，则敌灰飞烟灭；防守，则城固若金汤。枪兵聚，坦克轰，击垮的不是军队，是敌人的意志。

正所谓咸鱼终于翻身时，屡战屡败，但屡败屡战的卿学姐终于学会了暴兵一技，后获名暴兵狂魔。

时下正值开学之初，兵锋正锐，卿学姐与沈宝宝会战于暴雪平台。

战况可谓惨烈万分，沈宝宝虽然依靠卓越的技艺取得了前期的优势，然而卿学姐不悲不弃，本着暴兵的原则，终于在人口上超越了沈宝宝。

双拳难敌四手，沈宝宝终败于枪兵山下。

人逢失意时，正是成功始。惜有越王卧薪尝胆，今有沈爷日夜推敲。功夫不负有心人，沈爷终于掌握了克制卿学姐的办法，重新登上了集训队SC2的王座。

沈宝宝一共有2n个兵，每个兵有不同的攻击力，并且恰好这些兵的攻击力能构成2n的一个排列。

这些兵排成2*n的矩阵A，并且A中每个位置都要比这个位置的上面和左面大，即A[i][j]>A[i-1][j] i>1，并且A[i][j]>A[i][j-1] j>1。

有了这样的矩阵，沈宝宝终于可以以少胜多，打败卿学姐了。

对于n=5

这样的矩阵有一个解：

1 2 4 6 7

3 5 8 9 10

天行廖，也就是人尽皆知的772002，很喜欢数学题。

现在天行廖给沈宝宝出了个问题，对于沈宝宝的2n个兵，有多少种阵型能干死卿学姐。

沈宝宝忙着打SC2，所以这个问题就交给了你。

Input

第一行T，表示有T组数据，T<=100000。

接下来T行，每行一个整数n，n<=100000，表示沈宝宝有2n个兵

Output

一个答案，表示方案数，但是答案太大了，所以答案需要 mod 1e9+9。

Samples

1
3

5

Resources

每周一题 div2