自上而下

   我们有这样一个图。我们要找到从顶部结点到达底部结点的路径。首先,我们选择最高节点作为开始。之后的任何节点,我们可以沿着蓝色边缘水平或向下到达下一个节点。当我们到达底部节点时结束。之后我们可以再次选择一条路继续走。请注意,我们不能重复走一条已经走过的通路。
   好吧，你来算算有多少条路径？

第一行是一个整数T(1 < = T < = 1000),这表明有T测试用例。
下一行是对应每个测试用例,只有一个整数N(1 < = N < = 100 8611)表示图size的大小。

  每个测试用例,你应该输出有多少条下降路径.因为答案可能会非常大，所以输出结果请取余 1008611。(数据类型用long long 。输出用%lld)Hint【提示】：比如size=3的时候，如下图所示

3
1
2
10

2
8
168276