Shell sort is an efficient sorting algorithm that can be viewed as a grouped insertion sort. We briefly introduce the algorithm below:

Suppose we need to sort a sequence $A_{0\dots n-1}$ of length $n$ in ascending order. First, we determine an integer $m$ and a sequence $d$ of length $m$ that is strictly decreasing and ends with $1$, which serves as the gap sequence. Then, we perform $m$ rounds of operations.

For the $i$-th round, let $t=d_i$. We consider dividing $A$ into $t$ groups as evenly as possible. Specifically, we assign elements to groups based on their indices modulo $t$, and then perform an insertion sort on the elements within each group.

Specifically, you can refer to the following C++ code:

void bubble_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]);
        bubble_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();
    }
}

The work function represents one round of operations with parameter $t = d[i]$.

Given two integers $n$ and $m$, and a gap sequence $d$ of length $m$, you need to calculate the maximum value of the variable swap_count (the number of swaps performed) across all permutations of length $n$ after running the shell_sort function. Additionally, you need to provide the number of permutations that achieve this maximum value.

Both answers should be taken modulo $10^9+7$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $m$ integers, where the $i$-th integer represents $d_i$.

Output

One line containing two integers: the maximum number of swaps and the number of permutations that achieve this maximum. Both answers should be taken modulo $10^9+7$.

Examples

Input 1

5 2
2 1

Output 1

7 2

Note 1

The two permutations are $[3,5,2,4,1]$ and $[5,2,4,1,3]$.

Subtasks

For all data, $2\le n\le 30, 1\le m\le 10, d_1\le 10, d_m=1$, and $\forall i=1,2,\dots,n-1$, $d_i > d_{i+1}$ holds.

• Subtask 1 (18 pts): $n\le 8$.
• Subtask 2 (27 pts): $n\le 16$.
• Subtask 3 (21 pts): $n\le 22$.
• Subtask 4 (10 pts): $m=2$.
• Subtask 5 (24 pts): No special restrictions.