쪼개기와 합치기

시간 제한1초메모리 제한512 MB

요약

1xL 판을 1x1과 1x2 조각으로 채운 두 상태가 주어질 때, 분할과 병합으로 한 상태를 다른 상태로 바꾸는 최소 연산 횟수와 그 방법의 수를 구한다.

문제

$1 \times L$ 격자가 $1 \times 1$ 조각과 $1 \times 2$ 조각으로 나누어져 있다.

두 가지 연산을 수행할 수 있다. $1 \times 2$ 조각 하나를 $1 \times 1$ 조각 두 개로 쪼개는 연산과 이어 붙은 $1 \times 1$ 조각 두 개를 $1 \times 2$ 조각 하나로 합치는 연산이다.

격자의 초기 상태와 목표 상태가 주어졌을 때 수행해야 하는 연산의 최소 횟수와 그 횟수로 상태를 바꾸는 방법의 가짓수를 구한다.

첫 번째 줄에 격자의 길이 $L$ 이 주어진다 ( $1 \le L \le 3000$ ).

두 번째 줄에 초기 상태의 조각 수 $n$ 이 주어진다 ( $1 \le n \le L$ ).

세 번째 줄에 $n$ 개의 수 $a_1, a_2, ..., a_n$ 이 주어진다. 왼쪽 조각부터 순서대로 적은 각 조각의 길이이며 각 수는 1 또는 2이다. $n$ 개 수의 합은 $L$ 이다.

네 번째 줄에 목표 상태의 조각 수 $m$ 이 주어진다 ( $1 \le m \le L$ ).

다섯 번째 줄에 $m$ 개의 수 $b_1, b_2, ..., b_m$ 이 세 번째 줄과 같은 방식으로 주어진다.

첫 번째 줄에 필요한 연산의 최소 횟수와 그 횟수로 상태를 바꾸는 방법의 가짓수를 공백으로 구분해 출력한다. 가짓수가 커질 수 있으므로 $1000000007$ 로 나눈 나머지를 출력한다.