题目描述

东哥给你一个长度 $n$，要求你统计长度为 $n$ 且由大写字符组成的字符串中，满足以下条件的字符串数量：

1. 包含子串 AC 。
2. 不包含子串 WA 。

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

输入格式

第一行一个整数 $T\ (1 ≤ T ≤ 114514)$，表示测试用例的数量。

对于每组测试用例：

• 第一行一个整数 $n\ (1 ≤ n ≤ 114514)$，表示字符串长度。

输出格式

一个整数，表示满足条件的字符串数量，对 $10^9 + 7$ 取模。

4
1
2
3
114514

0
1
51
240541648