| 问题描述 |
|---|
有一窝有个性的蚂蚁（共a只）决定要搬家，从当前地点到目的地需要总共翻过b座高山。 每当翻越一座高山时（例如第i座），就会有ci种不同的路线可供选择，而这a只蚂蚁会很个性地分别从中选择一条自己喜欢的路线，因为每条路线都很宽，所以可以有多只蚂蚁选择相同路线。 问这一窝蚂蚁到达目的地有多少种不同的走法？ 由于答案非常大，所以只要输出答案除以100000007的余数。 |
| 输入描述 |
一个正整数n，表示案例的数量。（n<=1000） 每组案例先有两个正整数a、b，分别表示蚂蚁的数量和高山的数量（a<=1000000, b<=1000） 然后是b个正整数c1~cb，表示翻过每一座高山分别有多少种不同的路线可供选择。（ci<=1000000） |
| 输出描述 |
针对每组案例，输出一个整数，表示不同的走法数量除以100000007的余数。 每组案例输出完都要换行。 |
| 样例输入复制样例 |
1 2 3 1 2 4 |
| 样例输出 |
64 |
| 提示说明 |
2只蚂蚁经过第1座山，有1条道路可以选择，所以只有唯一的路线可供选择，那就是这2只蚂蚁都走这1条道路。经过第2座山，每只蚂蚁都可以从2条道路中任选1条，所以一共有2*2=4种选择。经过第3座山，每只蚂蚁都可以从4条道路中任选1条，所以一共有4*4种选择。综上，翻过这3座山，共有1*4*16=64种选择。 |
| 相关 |