#P1386. 座位安排
座位安排
题目描述
给 个人安排座位,先给每个人一个 的编号,设第i个人的编号为 (不同人的编号可以相同),接着从第一个人开始,大家依次入座。
第 个人来了以后尝试坐到 ,如果 被占据了,就尝试 , 也被占据了的话就尝试 ,……,如果一直尝试到第 个都不行,该安排方案就不合法。
然而有 个人的编号已经确定(他们或许贿赂了你的上司…),你只能安排剩下的人的编号。求有多少种合法的安排方案。由于答案可能很大,只需输出其除以 后的余数即可。
输入格式
第一行一个整数 ,表示数据组数;
对于每组数据,第一行有三个整数,分别表示 ;
若 不为 ,则接下来一行有 对整数,,其中第 对整数 表示第 个人的编号必须为 。
输出格式
对于每组数据输出一行,若是有解则输出 YES
,后跟一个整数表示方案数 ,注意,YES
和数之间只有一个空格;否则输出 NO
。
2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10
YES 4
NO
提示
对于 的数据 ,;
对于 的数据 ,,,, 且保证 互不相同。