题目描述

初始时，编辑器中有一个仅包含字符 * 的字符串，剪贴板为空。

你可以进行以下两种操作，每种操作均计为一次操作：

• (Ctrl+A)+(Ctrl+C)：将编辑器中的整个字符串复制到剪贴板中，覆盖剪贴板原有的内容。该操作不会改变编辑器中的字符串。

• Ctrl+V：将剪贴板中的字符串拼接到编辑器中字符串的末尾。只有剪贴板非空时才能执行该操作。

求恰好进行 $n$ 次合法操作后，编辑器中字符串长度的最大可能值。

由于答案可能很大，你只需输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行一个正整数 $T$ 表示测试数据组数。

接下来 $T$ 行，每行一个整数 $n$ 表示总操作次数。

输出格式

输出 $T$ 行，每行输出对于每个 $n$ 能得到的字符串长度最大值对 $10^9+7$ 取模的结果。

样例

1
6

9

样例解释

依次进行 (Ctrl+A)+(Ctrl+C)、两次 Ctrl+V、(Ctrl+A)+(Ctrl+C)、两次 Ctrl+V。

编辑器中的字符串长度依次为 $1,2,3,3,6,9$，因此答案为 $9$。

数据规模与约定

本题共 20 个测试点，每个测试点 5 分。

对于全部测试数据，$1\le T\le 1000$，$0\le n\le 10^{15}$。

原题链接

原题链接