咩咩今天卷了一整天的幸运九十九，躺在床上还在想没做出来的题，结果根本睡不着！但是为了赶上早八的课，咩咩决定数羊，但是她不想就那么简单的数羊，那样无法在睡觉的时候动脑子，于是她开始想，现在有一头羊，它每年年初就会生小羊，小羊从第四个年头开始，每年年初也能开始生小羊，那么第一年就有1头羊，第二年有2头羊，第三年有3头羊，第四年有4头羊，第五年有6头羊。。。。。咩咩睡着了，但她睡醒了之后又开始想问题了，如果到了第n年，那有几头羊了嘞？(假设羊长生不老，根本死不了)。

Input

第一行一个整数T $1\leq T\leq 1e6$ . 随后T行，每行一个整数n($1\leq n\leq 400$)

Output

每行一个整数，结果要对1e9+7取模

Samples

2
1
2

1
2

Limitation

1s, 1024KiB for each test case.