G 共同富裕

题目描述

宇宙无敌霸王龙帝国有 $n$ 个臣民，臣民 $i$ 拥有 $a_i$ 单位的财富。

身为恐龙大王，大笨龙希望所有臣民都拥有一样的财富，于是他选了三个整数 $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$。

第三行一个整数 $1$ 或 $2$，表示询问类型。

输出格式

若询问为 $1$，输出一行一个整数，表示最少操作次数；

若询问为 $2$，输出两行，每行一个整数，分别表示最少操作次数和方案数对 $10^9+7$ 取模的结果。

输入输出样例

3
1 2 3
2

2
16

说明/提示

【样例 1 解释】

一种可行的方案为：$(l,r,x)=(1,1,1),(3,3,-1)$。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（10 point）：$n=2$，询问类型为2。
• Subtask 2（10 points）：$n=3$，询问类型为2。
• Subtask 3（10 points）：保证 $a$ 单调不升或单调不降，询问类型为1。
• Subtask 4（10 points）：$n\le 10$，询问类型为1。
• Subtask 5（10 points）：$n\le 16$，询问类型为1。
• Subtask 6（10 points）：保证 $a$ 单调不升或单调不降，询问类型为2。
• Subtask 7（10 points）：$n\le 10$，询问类型为2。
• Subtask 8（10 points）：$n\le 16$，询问类型为2。
• Subtask 9（20 points）：无特殊限制，询问类型为2。

对于 $100\%$ 的数据，$1\le n\le 18$，$-10^9\le a\le 10^9$。