该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个只含数字的字符串，例如 $1233$ , 其奇数位的数位和为: $1+3=4$ , 偶数位的数位和位 $2+3=5$ (奇数位指下标是奇数的位置，偶数位指下标是偶数的位置，下标从 $1$ 开始。)

定义一个数字 $s$ 的奇偶权值 $f(s)$ 为：

$$f(s)=\Bigl(\text{奇数位数字之和}\Bigr)\times\Bigl(\text{偶数位数字之和}\Bigr) $$

例如：

f(1233)= (1+3)\times(2+3)=4\times 5=20

现在给定多个 $n$ ，请你分别计算：

所有长度为 $n$ 的数字串（允许前导零）的奇偶权值之和。

答案可能很大，请对 $10^9+7$ 取模后输出。

输入格式

第一行输入一个整数 $T$ ，表示测试数据组数。

接下来 $T$ 行，每行输入一个正整数 $n$ 。

输出共 $T$ 行。

对于每组数据，输出一个非负整数，表示所有长度为 $n$ 的数字串的奇偶权值之和对 $10^9+7$ 取模后的结果。

2  
2  
3

2025  
40500