在半人马星系，有M*N个星球，它们排成了M行N列，每个星球与其上下左右的星球都有一条星际航道相连，每个星球从属于一个国家，同一个国家中的所有星球都可以通过使用星际之门相连在一起。
现在小渡想从坐标为(1,1)的星球（左上角）航行到坐标为(M,N)的星球，为了体验星际旅行的美妙感觉，他想使自己通过星际之门和通过航道的次数之和为P，现在问他有多少种旅行方法可以满足要求。输出结果对1000007取余。
（注意旅行次序相同的方案当成同一种方案）
星际旅行
Input
第一行输入一个整数T（T<=20)表示测试数据的组数
每组测试数据的第一行是三个整数M,N,P，分别表示星球有M行，N列，小渡想通过星际之门和通过航道的次数之和为P(1<=M,N<=10,P<=100000000)
随后是一个M行N列的矩阵，代表着该处星球所属国家的编号（编号不超过20）
每组测试数据的第一行是三个整数M,N,P，分别表示星球有M行，N列，小渡想通过星际之门和通过航道的次数之和为P(1<=M,N<=10,P<=100000000)
随后是一个M行N列的矩阵，代表着该处星球所属国家的编号（编号不超过20）
Output
输出满足要求的旅行方案数
输出结果对1000007取余。
输出结果对1000007取余。
Sample Input
1
2 2 3
1 1
1 1
Sample Output
7