题目描述

小A想将一个正整数 $n$ 拆分成若干个正整数之和，并最大化拆分后的所有数之积。

请你计算最大乘积对 $10^9$ 取模的结果。

输入格式

第一行一个正整数 $t$，表示数据组数。

接下来 $t$ 行，每行一个整数 $n$。

输出格式

对于每组数据，输出一行一个整数，表示最大乘积对 $10^9$ 取模的结果。

样例输入

3
5
8
100

样例输出

6
18
755407364

数据范围

$1 \le t \le 10^4$，$1 \le n \le 10^6$。