시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 76 17 15 28.846%

문제

   * * *
×    * *
 -------
   * * *
 * * *
 -------
 * * * *

위와 같은 연산식의 *을 주어진 숫자로 바꿔서 옳은 식을 만들 수 있는 경우의 수를 구해보자.

예를 들어 각 줄의 별 개수가 각각 3, 2, 3, 3, 4개이고 사용할 수 있는 수가 2,3,4,6,8인 경우와 별 개수가 각각 3,3,3,3,3,5개이고 사용할 수 있는 수가 1,2,3,4,5,9인 경우의 가능한 수식은 다음과 같다.

   2 2 2         1 1 1
×    2 2    ×    1 1 1
 -------     ---------
   4 4 4         1 1 1
 4 4 4         1 1 1
 -------     1 1 1 
 4 8 8 4     ---------
             1 2 3 2 1

입력

입력의 첫 번째 줄에 연산식에 있는 줄의 총 개수 N이 주어지고, 그 다음줄에는 각 줄의 별 개수를 나타내는 N개의 정수 S1, S2, S3, …, SN N이 공백으로 구분되어 주어진다. 그 다음 줄에는 사용할 수 있는 수의 개수 K가 주어진다. 마지막으로 세 번째 줄에는 사용할 수 있는 수 K개(각각 1,2, …, 9중 하나, 중복은 없다)가 공백으로 구분되어서 주어진다.

*수식은 올바른 형태만 주어지며(N=S2+3이란 뜻이다), 1 ≤ S1 ≤ 5, 1 ≤ S2 ≤ 3이다.

출력

주어진 수들을 사용해서 수식을 올바르게 만들 수 있는 경우의 수를 출력한다.

예제 입력

5
3 2 3 3 4
5
2 3 4 6 8

예제 출력

1

예제 입력 2

6
3 3 3 3 3 5
6
1 2 3 4 5 9

예제 출력 2

77

힌트