Fady and Stable Arrays#12482
Fady is studying the stability of mathematical sequences. He defines an array to be stable if no two adjacent elements are equal. Conversely, if an array contains at least one pair of adjacent elements that are equal, it is considered unstable.
Recently, Fady received an array of length . If the array is unstable, he can perform the following operation any number of times (possibly zero) to try and change it:
Choose an index (1 \le i < |a|) such that a_i = a_{i+1}.
Remove these two adjacent elements and insert a single element with the value a_i + 1 in their exact place.
Note that the length of the array decreases by after each operation, and the indices of all subsequent elements shift accordingly.
Fady wants to know the total number of distinct stable arrays he can form by applying some sequence of operations. Two stable arrays are considered distinct if they have different lengths, or if there is at least one index where their elements differ.
Since the answer can be incredibly large, Fady needs your help to compute it modulo 10^9 + 7.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains a single integer (1 \le n \le 10^5) — the length of the array.
The second line of each test case contains integers a_1, a_2, \dots, a_n (1 \le a_i \le \mathbf{80}) — the elements of the array.
It is guaranteed that the sum of over all test cases does not exceed 10^5.
For each test case, output a single integer — the number of distinct stable arrays Fady can form, modulo 10^9 + 7.
Example 1
In the second test case, the initial array is [5, 4, 3, 2, 1, 1]. Fady is forced into a strict chain reaction. Merging the s creates an unstable array [5, 4, 3, 2, 2]. This forces him to merge the s to make [5, 4, 3, 3], and so on, until the array completely collapses into a single element . This is the only stable array he can form, so the answer is .
In the third test case, the initial array is [2, 1, 1, 2]. Merging the s creates an unstable array [2, 2, 2]. From here, Fady has two choices:
Merge the left pair of s to form the stable array .
Merge the right pair of s to form the stable array .
Thus, there are exactly distinct stable arrays.
In the fourth test case, the distinct stable arrays Fady can form are:
[3, 2, 1, 2]
[2, 3, 1, 2]
[2, 1, 3, 2]
[3, 1, 3]
[2, 1, 2, 3]
Subtask 1 (100 points): \sum n \le 400
Subtask 2 (150 points): a_1 = a_2 = \dots = a_n
Subtask 3 (150 points): No additional constraints.