牛牛管理着一片农场，在这片农场的一侧有着 块栅栏排成一排，为了给单调的牧场生活增添一份乐趣，牛牛决定为这 块栅栏涂色。 现在，牛牛在牧场中一共找到了 种不同颜料，每种颜料都有自己的推荐方案，如：第 种颜料罐上写着，在这种颜料后如果紧跟 这 种颜料中的一个，整体色调就会显得不那么美丽。 那么，在满足上述前提下，牛牛最终完成的美丽的涂色一共会有多少种方案？ 由于答案可能很大，所以只需要求出对 取模后的结果。

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。对于每组测试数据，第一行输入三个正整数 ，代表栅栏总数，颜料总数以及每种颜料后不能紧跟的颜料种类数。接下去 行，每行输入 个正整数，，代表该种颜料后不能紧跟这 种颜色。

输出描述:

对于每组测试数据，输出一行一个数字表示牛牛的涂色方案。