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

수영 과목을 Pass한 재우는 MatKor 부원들과 함께 회식에 가게 되었다. 맛있는 고기를 실컷 먹으며 즐거운 시간을 보낸 뒤, 후식으로 모두 비빔냉면을 주문했다. 그냥 먹기에는 아쉬웠던 MatKor 부원들은 비빔냉면 한 그릇에 온갖 매운맛을 더해 무작위로 섞은 뒤 재우에게 먹이기로 했다.

비빔냉면을 맵게 만들기 위해 MatKor 부원들은 매운맛이 나는 재료를 $N$가지 준비했다. 모든 재료는 한 조각 단위로 비빔냉면에 넣을 수 있다. 처음에 비빔냉면에는 $N$가지 재료가 각각 0조각씩 들어 있다.

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

$M$명의 부원은 각자 비빔냉면에 넣고 싶은 재료를 정해 두었다. 싸움이 나지 않도록 공평한 비빔냉면을 만들기 위해, 부원들은 아래 시행을 정확히 $K$번 반복하기로 했다.

• $M$명의 부원 중 한 명을 균등한 확률로 뽑는다.
• 뽑힌 부원이 좋아하는 모든 $i$번 재료에 대하여, $1$ 이상 $S_i-1$ 이하의 정수 중 하나를 균등한 확률로 고르고, 그 개수만큼 $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+3$번째 줄까지 각 줄에는 부원이 좋아하는 재료에 대한 정보가 주어진다. 각 줄의 처음에는 부원이 좋아하는 재료의 수 $T$($1\le T\le N$)가 주어지고, 이어서 부원이 좋아하는 모든 재료의 번호 $X_1, X_2, \cdots, X_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$)라고 하자. 이 값을 $10^9+7$로 나눈 나머지는 $q \cdot q^{-1}\equiv 1 \pmod{10^9+7}$를 만족하는 정수 $q^{-1}$를 사용하여 $p \cdot q^{-1} \pmod{10^9+7}$로 정의한다. 확률이 정수이면 $q=q^{-1}=1$이므로 답은 $p \pmod{10^9+7}$이다.

주어진 조건에서 확률은 분모가 $10^9+7$의 배수가 아닌 유리수로 나타낼 수 있다.

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