문제 제목: 민초 상인 최승민

36기 최승민, 그는 튜링에서 후배들에게 머신 러닝에 대한 수많은 강의를 하고, 여러 끔직한 과목들을 버텨온 유망한 정보충이다. 그러나 승민이에게는 일반인들은 이해조차 할 수 없는 끔직하도록 어두운 면이 있다.
그렇다. 승민이는 매일 디저트로는 설빙에서 민트초코빙수(민초)를 먹고, 음료로는 데자와를 마신다는 것이다(구웨에에엑). 
승민이는 나코더 친구들을 민초와 데자와의 길로 이끌려고 했으나 실패하자, 같이 민초의 길을 걷는 준호와 함께 전국적으로 민초와 데자와 사업을 시작하려 한다.
광고가 어찌저찌 성공하여 N명의 고객들이 승민이에게 민초와 데자와를 사겠다고 했다. 일반인은 속이 단련되어있지 않아서 민초와 데자와를 같이 먹을 수 없고 한 번에 두 종류 중 하나만 먹을 수 있다. 그래서 시킬 때도 민초와 데자와 중 하나만 시킨다.
i번째 고객은 최대 a_i개의 개의 민초와 b_i개의 데자와를 먹을 수 있다. 고객들은 이미 보증금을 내서 최소 1개 이상의 제품을 사야한다. 승민이는 항상 충분한 민초와 데자와를 갖고 있다.
승민이와 준호의 최대 관심사는 데자와가 아닌 민초라서 C명 이상의 고객들이 민초를 사기를 바란다.
고객들이 주문을 바꿀 때가 많기 때문에 승민이는 "최소 C명 이상의 고객들이 민초를 구매하는 방법의 수는 무엇인가?"를 알고싶다. 승민이의 민초 데자와 사업을 도와주자!

Input
첫 줄에 두 개의 정수 N, C가 주어진다. (1 ≤ N ≤ 100 000, 1 ≤ C ≤ 20).
두 번째 줄에 N개의 정수 a_i가 주어진다. (1 ≤ ai ≤ 1 000 000 000).
세 번째 줄에 N개의 정수 b_i가 주어진다. (1 ≤ bi ≤ 1 000 000 000).
네 번째 줄에 고객들이 바꾼 주문 Q개가 입력된다. (1 ≤ Q ≤ 100 000). (1 ≤ P ≤ N),(1 ≤ aP ≤ 1 000 000 000) , (1 ≤ bP ≤ 1 000 000 000). 
이후 Q개의 줄이 입력된다. 각 줄에는 세 개의 정수 P, a_P, b_P가 주어진다. 이는 P번째 고객이 구매할 최대 민초의 개수가 a_P개, 최대 데자와의 개수가 b_P개임을 의미한다.

Output
각 주문이 바뀔 때마다 가능한 고객들의 구매 방법의 가짓수를 10007로 나눈 나머지를 출력한다.

IO example 1
입력
2 2
1 1
1 1
1
1 1 1
출력
1
IO example 2
입력
2 2
1 2
2 3
2
1 2 2
2 2 2
출력
4
4
IO example 3
입력
4 2
1 2 3 4
1 2 3 4
1
4 1 1
출력
66

추가 설명: 예제 3의 경우 2명이 민초를 사는 경우 36가지 3명이 사는 경우 24가지 4명이 사는 경우 6가지 해서 총 66가지이다. 즉, 각 고객이 산 물품의 종류나 개수가 다르면 세는 것이다.