#P18823. [Croatian CPC2017] Cod

[Croatian CPC2017] Cod

[Croatian CPC2017] Cod

题目描述

在一场游戏中,有 nn 名玩家相互战斗。玩家 xx 的成绩由两个整数 fx,dxf_x,d_x 表示:fxf_x 是他击败其他玩家的总次数,dxd_x 是他被其他玩家击败的总次数。

每当玩家 xx 击败玩家 yy,fxf_x 和 dyd_y 就各增加 11。被击败的玩家会重新出现并继续游戏。玩家不能击败自己,两次击败事件也不会同时发生。所有玩家的两项计数最初均为 00。一旦有玩家恰好完成 nn 次击败,游戏立即结束。

游戏结束后,成绩表包含 nn 行、两列,每行依次给出一名玩家的 fx,dxf_x,d_x。表中的行按照以下规则排序:先按 fxf_x 从大到小排列;若 fxf_x 相同,则按 dxd_x 从小到大排列。

现在成绩表中的一些数值被擦除了。请计算有多少张不同的完整成绩表可能产生给定的残缺成绩表,答案对 109+710^9+7 取模。只统计数值表格的区别,不区分玩家身份或具体战斗过程。

输入格式

第一行包含一个整数 nn(2≤n≤102\le n\le10)。

接下来 nn 行,第 kk 行包含两个整数 fk,dkf_k,d_k(−1≤fk≤n-1\le f_k\le n,−1≤dk≤n2-1\le d_k\le n^2),表示残缺成绩表的第 kk 行。被擦除的数值用 −1-1 表示。

保证输入至少能由一场按上述规则正常结束的游戏产生。

输出格式

输出一个整数,表示可能的完整成绩表数量对 109+710^9+7 取模的结果。

样例 1

输入

2
-1 -1
-1 -1

输出

2

样例 2

输入

3
-1 -1
-1 1
1 2

输出

2

样例 3

输入

4
4 3
3 -1
2 -1
-1 2

输出

14

样例说明

样例 1 的两张可能成绩表分别是 (2,0),(0,2)(2,0),(0,2) 和 (2,1),(1,2)(2,1),(1,2)。