g6-07915. 打家劫舍·计数 未做

一条街上有 $n$ 间房，第 $i$ 间房里有 $a_i$ 元现金。小偷不能偷相邻的两间房。求最多能偷到多少钱，以及有多少种偷法能达到这个最大金额。两种偷法不同，当且仅当被偷的房间集合不同。方案数对 $10^9+7$ 取模。

第一行一个整数 $n$（$1\le n\le 10^5$）。

第二行 $n$ 个整数 $a_1,\dots ,a_n$（$1\le a_i\le 10^4$）。

一行两个整数：最大金额、达到最大金额的方案数（对 $10^9+7$ 取模）。

输入 1

5
2 7 9 3 1

输出 1

12 1

输入 2

3
1 2 1

输出 2

2 2

对于所有数据，$1\le n\le 10^5$，$1\le a_i\le 10^4$。