Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#2220. Travel

统计

题目描述

有 $N$ 个人出去旅行,第 $i$ 个人去 $A$ 国有 $A_i$ 种游玩方式,去 $B$ 国有 $B_i$ 种游玩方式,问至少有 $C$ 个人去 $A$ 国的情况下,所有人的游玩方式有多少种不同的可能。

两种所有人的游玩方式不同当且仅当存在一个人选择的游玩方式不同,或选择去的国家不同。

接下来有 $P$ 次修改,每次修改一个人的 $A_i$ 和 $B_i$。

输入格式

第一行两个正整数,表示 $N$,$C$,含义如题所示。

接下来一行 $N$ 个整数,第 $i$ 个整数表示 $A_i$。

接下来一行 $N$ 个整数,第 $i$ 个整数表示 $B_i$。

接下来一行一个正整数表示 $P$。

接下来 $P$ 行,每行三个整数 $i$,$x$,$y$,表示修改 $A_i$ 为 $x$,$B_i$ 为 $y$。

输出格式

对每次修改输出一行一个整数,表示总方案数 $mod$ $10007$

样例

样例输入

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

样例输出

66

数据范围与提示

对于 $100\%$ 的数据满足:$A_i$,$B_i$,$x$,$y$ 在 $int$ 范围内。

ID N C P
1 943 9 1229
2 816 11 1595
3 709 19 1219
4 52406 7 67687
5 85718 13 81220
6 90929 18 66630
7 63156 12 63169
8 90452 8 56691
9 73893 9 96448
10 70363 20 93259