题目描述

定义字符串序列 $F_1,F_2,\ldots$ 如下：

计算 $F_n$ 有多少个本质不同的子序列，对 $10^9+7$ 取模。

输入格式

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

接下来 $T$ 行，每行一个正整数 $n\ (1\le n\le 10^{18})$，表示一组数据。

输出格式

一行 $T$ 个整数，表示答案。

样例

样例输入

4
1 2 3 100000

样例输出

4 17 226 73460621

样例解释

$F_1=\text{dt}$，$F_2=\text{dtdtt}$，$F_3=\text{dtdttdtdttt}$。

数据范围

保证 $1\le T\le 10$，$1\le n\le 10^{18}$。