牛牛管理着一片农场，在这片农场的一侧有着 n 块栅栏排成一排，为了给单调的牧场生活增添一份乐趣，牛牛决定为这 n 块栅栏涂色。 现在，牛牛在牧场中一共找到了 m 种不同颜料，每种颜料都有自己的推荐方案，如：第 i 种颜料罐上写着，在这种颜料后如果紧跟 c_ 1, c_ 2,..., c_ k 这 k 种颜料中的一个，整体色调就会显得不那么美丽。 那么，在满足上述前提下，牛牛最终完成的美丽的涂色一共会有多少种方案？ 由于答案可能很大，所以只需要求出对 10 ^ 9+ 7 取模后的结果。
本题为多组测试数据，第一行输入一个正整数 T( 1≤ T≤ 100) ，代表测试数据组数。 对于每组测试数据，第一行输入三个正整数 n, m, k( 1≤ n≤ 1000, 1≤ k< m≤ 10 ，代表栅栏总数，颜料总数以及每种颜料后不能紧跟的颜料种类数。 接下去 m 行，每行输入 k 个正整数， c_ 1, c_ 2,..., c_ k( 1≤ c_ i≤ m) ，代表该种颜料后不能紧跟这 k 种颜色。
对于每组测试数据，输出一行一个数字表示牛牛的涂色方案。
1 2 2 1 1 1
2
考点：动态规划
数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出
推荐方向：动态规划
本题切入点
涂色方案数按位置递推：dp[i][c] 表示第 i 块用颜色 c 的方案数，转移时排除被禁的后继颜色，全程取模。
把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。
思路框架（动态规划 通法 · 非本题专属）
实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。
复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)
该范式的通法易错点
对照本题
样例 1
1 / 2 2 1 / 1 / 12解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：贝壳找房2023届校招开发类试卷。