「EZEC-10」Equalization

给你一个长为 $n$ 的数组 $a_1,a_2,\ldots,a_n$。 你可以任选三个整数 $l,r,x\ (1\le l\le r\le n$，$x\in \mathbb Z)$，并将 $a_l,a_{l+1},\ldots,a_r$ 均加上 $x$，称为一次操作。 问最少进行几次操作，才能使 $a$ 中所有元素均相等？并求出能使操作次数最少的不同方案数。 由于方案数可能很大，请对 $10^9+7$ 取模。 **两种方案相同，当且仅当两方案每次操作选择的 $(l,r,x)$ 均相同。** **特别地，不进行任何操作也算一种方案。**

第一行一个整数 $n$。 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第一行一个整数，表示最少操作次数。 第二行一个整数，表示方案数对 $10^9+7$ 取模的结果。

3
1 2 3

2
16

**【样例 1 解释】** 一种可行的方案为：$(l,r,x)=(1,1,1),(3,3,-1)$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（1 point）：$n=2$。 - Subtask 2（5 points）：$n=3$。 - Subtask 3（14 points）：保证 $a$ 单调不升或单调不降。 - Subtask 4（20 points）：$n\le 10$。 - Subtask 5（20 points）：$n\le 16$。 - Subtask 6（40 points）：无特殊限制。 对于 $100\%$ 的数据，$1\le n\le 18$，$-10^9\le a\le 10^9$。