题目描述

有一个 $1\times L$ 的网格，它被若干个 $1\times1$ 小块和 $1\times2$ 小块完整地划分。

你可以进行以下两种操作：

1. 将一个 $1\times2$ 小块拆成两个相邻的 $1\times1$ 小块；
2. 将两个连续相邻的 $1\times1$ 小块合并成一个 $1\times2$ 小块。

给定网格的初始划分状态和目标划分状态，请求出：

• 将初始状态变成目标状态所需的最少操作次数；
• 恰好使用这么多次操作完成转换的方法数。

两种方法不同，当且仅当它们执行的操作序列不同；操作的位置或操作顺序不同，都视为不同方法。

例如，考虑一个长度为 $6$ 的网格，其初始状态如下：

目标状态如下：

先拆分一个 $1\times2$ 小块，再进行两次合并，共需 $3$ 次操作；能够以最少操作数完成转换的方法共有 $3$ 种。

输入格式

第一行包含一个整数 $L$，表示网格的长度。

第二行包含一个整数 $n$，表示初始状态中的小块数量。

第三行包含 $n$ 个整数

从左到右表示初始状态中各小块的长度。

第四行包含一个整数 $m$，表示目标状态中的小块数量。

第五行包含 $m$ 个整数

从左到右表示目标状态中各小块的长度。

输出格式

输出两个整数：

• 将初始状态变为目标状态所需的最少操作次数；
• 使用最少次数完成转换的方法数对 $1\,000\,000\,007$ 取模后的结果。

两个整数之间用一个空格分隔。

数据范围

并保证

样例

原题面没有单独给出样例输入输出。下面把题目描述中长度为 $6$ 的示例改写为标准输入输出形式。

输入

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

输出

3 3

说明

最少需要先拆分一个长度为 $2$ 的小块，再进行两次合并，共执行 $3$ 次操作。按最少操作数完成转换的操作序列共有 $3$ 种。