题目描述

设七位十进制数\(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。

来源

原创题