32239번 - 매운 음식을 못 먹는 재우가 비빔냉면을 먹으면? 서브태스크

문제

매운 음식을 못 먹는 재우가 비빔냉면을 먹으면? 쟤 우냐?

수영 과목을 Pass한 재우는 MatKor 부원들과 함께 회식에 가게 되었다. 맛있는 고기를 원 없이 먹으며 즐거운 시간을 보낸 뒤, 후식 메뉴로 모두 비빔냉면을 먹게 되었다. 하지만 그냥 먹기에 너무 아쉬웠던 MatKor 부원들은 하나의 비빔냉면에 온갖 매운맛을 첨가해 무작위로 섞은 뒤 한 명에게 먹이기로 했다.

어떻게든 매운맛이 나는 비빔냉면을 만들기 위해 MatKor 부원들은 매운맛이 나는 $N$가지의 재료를 준비했다. 모든 재료는 한 조각 단위로 비빔냉면에 넣을 수 있으며, 처음에 비빔냉면에는 $N$가지의 재료가 각각 0ドル$조각 포함되어 있다.

매운 음식을 전혀 먹지 못하는 재우의 혀는 신기하게도 $i$번 재료에 대해 $S_i$개의 조각을 먹을 때마다 해당 재료의 매운맛이 사라진다. 즉, 각 재료에 대해 $i$번 재료가 들어가지 않았거나 들어간 $i$번 재료 조각의 개수가 $S_i$의 배수라면, $i$번 재료에 대한 매운맛을 느끼지 않는다. 또한 재우는 모든 재료에 대해 매운맛이 느껴지지 않을 때 그 음식의 매운맛을 느끼지 않고, 한 재료라도 매운맛을 느끼면 그 음식의 매운맛을 느낀다.

$M$명의 부원들은 각자 비빔냉면에 넣고 싶은 재료들이 정해져 있다. 따라서 싸움이 나지 않도록 공평한 비빔냉면을 만들기 위해 아래와 같은 시행을 정확히 $K$번 거치며 비빔냉면을 만들기로 했다.

• $M$명의 부원 중 한 명을 균등한 확률로 뽑는다.
• 뽑힌 부원이 좋아하는 모든 $i$번 재료에 대하여 1ドル$ 이상 $S_i$ 미만의 정수 중 하나를 균등하게 골라 $i$번 재료 조각을 해당 개수만큼 추가한다.

매 시행은 독립적이므로, 이전에 뽑혔던 부원이 다시 뽑힐 수도 있다.

재우는 최악의 경우 자신이 매운 비빔냉면을 먹을 수도 있다는 생각이 들어 두려움에 떨기 시작했다. 재우가 매운맛을 느끼지 않고 냉면을 먹을 수 있을 확률을 계산해 보자.

입력

첫 번째 줄에 $N(1\le N\le 20)$이 주어진다.

두 번째 줄에 $S_1,S_2,\cdots ,S_N(2\le S_i\le 10^9)$이 공백으로 구분되어 주어진다.

세 번째 줄에 $M(1\le M\le 10^5)$이 주어진다.

네 번째 줄부터 $M$개의 줄에 걸쳐 각 부원이 좋아하는 재료에 대한 정보가 주어진다.

각 줄의 처음에 부원이 좋아하는 재료의 수 $T(1\le T\le N)$가 주어지며, 이어 부원이 좋아하는 모든 재료의 번호를 의미하는 $T$개의 정수 1ドル\le X_1<X_2<\cdots <X_T\le N$이 공백으로 구분되어 오름차순으로 주어진다.

다섯 번째 줄에 $K(1\le K\le 10^9)$가 주어진다.

출력

첫 번째 줄에 재우가 매운 맛을 느끼지 않고 냉면을 먹을 수 있을 확률을 10ドル^9+7$로 나눈 나머지를 출력한다.

기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

주어진 조건 내에서 확률이 정수 혹은 분모가 10ドル^9+7$의 배수가 아닌 유리수로 나타내어짐을 증명할 수 있다.

제한

서브태스크

노트

이 문제의 제목과 제목에 대한 답은 kidw0124의 아이디어이다.