题目背景

在收卷最后五分钟，pg 发现了卷子反面还有一道大题。

题目描述

求

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

输入格式

第一行一个正整数 $T$，为数据组数。

下面 $T$ 行，每行 $3$ 个整数，为 $n,m,p$。

输出格式

共 $T$ 行，每行一个整数，为答案。

2
10 12 11
30 20 25

25302
573830

提示

对于前 $10\%$ 的数据，$T=5~,~40 \le n,m,p \le 100$。

对于另外 $20\%$ 的数据，$T=50~,~100 \le n,m,p \le 5\times 10^4$。

对于另外 $20\%$ 的数据，$T= 20~,~4\times 10^6 \le n,m,p \le 5\times 10^6$。

对于另外 $50\%$ 的数据，$T=10^3~,~10^7 \le n,m,p \le 2\times 10^7$。