希尔排序（Shell Sort）是一种优秀的排序算法，可以被视为一种分组插入排序。下面简要介绍该算法：

假设我们需要将一个长度为 $n$ 的数组 $A_{0 \dots n-1}$ 按升序排序。首先，我们需要确定一个整数 $m$ 和一个长度为 $m$ 的递减序列 $d$（其中最后一个数为 $1$）作为步长序列，然后进行 $m$ 轮操作。

对于第 $i$ 轮操作，令 $t = d_i$，然后考虑将 $A$ 尽可能均匀地分成 $t$ 组。具体来说，我们将模 $t$ 同余的下标位置分为一组，然后在每组内执行插入排序。

void insert_sort(vector<int> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j && v[j] < v[j - 1]; j--) {
            swap(v[j], v[j - 1]);
            swap_count++;
        }
    }
}

void work() {
    for (int i = 0; i < t; i++) {
        vector<int> v;
        for (int j = i; j < n; j += t) v.push_back(A[j]);
        insert_sort(v);
        for (int j = i, k = 0; j < n; j += t, k++) A[j] = v[k];
    }
}

void shell_sort() {
    swap_count = 0;
    for (int i = 1; i <= m; i++) {
        t = d[i];
        work();
    }
}

work 函数代表参数为 $t = d_i$ 的一轮操作。

给定两个整数 $n, m$ 以及一个长度为 $m$ 的步长序列 $d$，你需要计算在对长度为 $n$ 的所有排列运行 shell_sort 函数后，数组元素交换次数（即变量 swap_count 的值）的最大值。此外，你还需要给出能够达到该最大值的排列数量。

答案需要对 $10^9 + 7$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 30, 1 \le m \le 10$)。

第二行包含 $m$ 个整数，其中第 $i$ 个整数表示 $d_i$。保证 $1 \le d_i \le 10$，$d_m = 1$，且对于所有 $1 \le i \le m - 1$ 都有 $d_i > d_{i+1}$。

输出格式

输出一行，包含两个整数，分别表示交换次数的最大值以及达到该最大交换次数的排列数量。答案需要对 $10^9 + 7$ 取模。

样例

输入 1

5 2
2 1

输出 1

7 2