题目描述

给你一个长为 $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$。