#P3581. [POI 2015] CZA

    ID: 4418 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>动态规划 DP2015POI(波兰)哈希 hashing

[POI 2015] CZA

题目描述

nn 个人(编号为 1n1 \sim n)围着圆桌坐成一圈。座位相邻的两个人,其编号之差的绝对值不可以超过 pp。他们之中有些人不喜欢别人。如果 aa 不喜欢 bb,那么 bb 不能坐在 aa 右边的那一个位置上。现在,假设第 nn 个人的座位已经固定,要给剩下的人安排座位,共有几种合法方案?

输入格式

第一行包含三个整数 n,k,pn,k,p1n1061\le n\le {10}^60k1050\le k\le {10}^50p30\le p\le 3)。接下来 kk 行,每行含两个整数 ai,bia_i, b_i1ai,bin1\le a_i, b_i \le naibia_i \neq b_i),表示 aia_i 不喜欢 bib_i。同一组 ai,bia_i,b_i 不会重复输入。

输出格式

输出一个整数,表示方案数模 109+7{10}^9+7 后的值。

输入数据 1

5 2 3
1 3
5 4

输出数据 1

6

提示

原题名称:Czarnoksiężnicy okrągłego stołu。