시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 551 109 75 28.958%

문제

1×L 격자가 있고, 1×L 격자는 1×1 조각과 1×2 조각들로 나누어져 있다.

당신은 2가지의 연산을 수행할 수 있는데, 그것은 1×2 조각을 쪼개 1×1조각 2개로 만드는 연산과, 연속하여 붙어 있는 1×1 조각 2개를 합쳐 1×2 조각 하나로 만드는 연산이다.

1×L 격자의 초기 상태와 만들고자 하는 상태가 주어졌을 때, 수행해야 하는 연산의 최소 횟수와 그 횟수만큼 연산을 수행해 격자의 상태를 올바르게 바꾸는 방법의 가짓수를 구하여라.

예를 들어, 1×6 격자가 있고 초기 상태가 다음과 같다고 하자.

이 격자를 아래와 같이 만들고자 할 때,

1×2 조각을 1×1 격자 2개로 나눈 후에 1×1 격자 2개를 하나로 합치는 연산을 2번 하면 총 3번 만에 변환을 마칠 수 있고, 이때 경우의 수는 3가지가 존재한다.

입력

첫 번째 줄에는 격자의 길이 L이 주어진다. (1 ≤ L ≤ 3,000)

두 번째 줄에는 처음에 있는 조각의 수 n이 주어진다. (1 ≤ n ≤ L)

세 번째 줄에는 n개의 수 a1, a2, ..., an이 주어진다. 이는 왼쪽 조각부터 차례대로 주어지는 조각의 길이이며, 모두 1 이상 2 이하이다. n개의 수의 합은 L이다.

네 번째 줄에는 만들어야 하는 상태에 있는 조각의 수 m이 주어진다. (1 ≤ m ≤ L)

다섯 번째 줄에는 m개의 수 b1, b2, ..., bm이 세 번째 줄과 같은 방식으로 주어진다.

출력

첫 번째 줄에 필요한 연산의 최소 횟수와 그 때 방법의 가짓수를 공백을 사이에 두고 출력한다. 방법이 많아질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

6
5
1 2 1 1 1
4
2 1 2 1

예제 출력 1

3 3