15902번 - Split and Merge

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개의 수 a₁, a₂, ..., a_n이 주어진다. 이는 왼쪽 조각부터 차례대로 주어지는 조각의 길이이며, 모두 1 이상 2 이하이다. n개의 수의 합은 L이다.

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

다섯 번째 줄에는 m개의 수 b₁, b₂, ..., b_m이 세 번째 줄과 같은 방식으로 주어진다.

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