解题思路

给定严格递增且互不相同的正整数数组，要求统计所有非空子序列，使得子序列中相邻两个元素的差都不等于 1。 由于数组有序且无重复，当我们把某个元素 a[i] 追加到一个已合法的子序列末尾时，唯一可能产生违例的情况就是前一个被选中的元素等于 a[i]-1。而 a[i]-1 若存在，只可能是 a[i-1]（因为数组严格递增）。因此只需分两类讨论：

• 若 a[i] == a[i-1] + 1：新子序列末尾不能是 a[i-1]，因此可追加的前缀子序列只能来自前 i-2 个元素。
• 否则：数组中不存在值为 a[i]-1 的元素，a[i] 可以接在前 i-1 个元素形成的任意合法子序列后面。

据此设计简单 DP：

题目内容

给定一个长度为 $n$ 的正整数数组 $a$ ，数组已按升序排列目元素互不相同 $(a_i<a_{i+1})$ 。

统计所有非空子序列(保持原序)，使得子序列中任意相邻两个元素之差均不等于 $1$ 的方案数。由于答案可能很大，请对 $10^9+7$ 取模后输出。

【名词解释】 子序列为从原序列中删除任意个(可以为零、可以为全部)元素得到的新序列。

输入描述

第一行输入整数 $T(1 ≦ T ≦ 10^3)$ ，表示测试用例数。

接下来 $T$ 组数据，每组两行:

1.第一行输入整数 $n(1 ≦n≦2×10^5)$ ;

2.第二行输入 $n$ 个两两互不相同且升序的正整数 $a_i(1 ≦a_i≦ 10^9)$ ;

保证所有测试用例中 $\sum n≦2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数——满足条件的非空子序列总数对 $10^9+ 7$ 取模的结果。

样例1

输入

2
5
1 2 4 5 7
4
1 2 3 4

输出

17
7

说明

对于 $[1,2,3,4]$ ，有 $7$ 个满足条件的非空子序列:

{$1$},{$2$},{$3$},{$4$},{$1,3$},{$2,4$},{$1,4$} 。