Description

Kanade 最近在打公主连结的活动。众所周知，活动中 Normal 难度的关卡有 $15$ 个， $1-4$ 关卡通关一次要耗费 $8$ 体力， $5-10$ 关卡通关一次要耗费 $9$ 体力， $11-15$ 关卡通关一次要耗费 $10$ 体力。每个玩家一天可以通关无限次关卡。

现在 Kanade 有 $n$ 体力，她想要把这些体力全部用在刷 Normal 关卡上，不剩余任何体力。请输出有多少种满足条件的方案。两种方案不同，当且仅当通关消耗某相同体力关卡的次数不同。

Input

第一行一个整数 $T\ (1\le T\le 10^4)$ ，表示数据组数。

接下来 $T$ 行，每行一个整数 $n\ (1\le n\le 10^{18})$ ，表示当前体力值。

对于每组数据输出一行，表示满足条件的方案数。由于这个方案数可能会很大，请输出它对 $10^9+7$ 取模后的值。

2
10
18

1
2

对于第二组数据，可以通关两次消耗 $9$ 体力的关卡，也可以通关一次消耗 $8$ 体力的关卡再通关一次消耗 $10$ 体力的关卡。

The 21st UESTC Programming Contest Preliminary