题目描述

设七位十进制数$A = \displaystyle\sum_{n=0}^{6} 10^n a_n; \phantom{x} a_i \in \{0,1 \cdots 9\}$满足如下条件：
（1）$a_6 > 0$；
（2）任意两位上的数均不相同，即$i \ne j \rightarrow a_i \ne a_j$；
（3）给定两个整数$x_1, x_2 \in \{-1, 0, 1 \cdots 9 \}$，要求每一位上的数与$x_1, x_2$均不相等。（$x_i = -1$则相当于该限制不存在）
给定$K \in \{2,3,4,5\}$，求$M = A^K \mod (10^9 + 7)$的最大值。

I/O格式

输入

第一行是一个正整数$T$，表示该测试文件内的数据组数；
之后$T$行，每行三个整数$x_1, x_2, K$，取值范围见“题目描述”部分。

输出

每组测试数据输出一行，每行一个整数$M_0$，表示$M$的最大值为$M_0$。

样例

输入

2
2 4 5
-1 1 3

输出

999968654
999999708

数据规模及约定

40%的数据：$T = 1$；
70%的数据：$T \le 10$；
100%的数据：$T \le 100$。
时间限制1s，空间限制64MB。

来源

原创题