Bored piglet has an integer sequence $$$a_1,a_2,\cdots,a_n$$$.
He wants to partition this sequence into several intervals, denoted as $$$[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$$$ (the value of $$$m$$$ is chosen arbitrarily), satisfying all of the following conditions:
The first line contains a single integer $$$n$$$ ($$$1\le n\le10^5$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1\le a_i\le10^9$$$).
Print a single integer, the number of valid partitions modulo $$$10^9+7$$$.
61 2 3 2 2 1
14
121 1 2 3 2 2 1 9 1000000000 23 24 25
284
We can use the inclusion-exclusion principle on two sets to calculate the answer of the first example:
Partitioning $$$a_1,a_2,\cdots,a_6$$$ into $$$m$$$ intervals is equivalent to choosing $$$m-1$$$ gaps among the $$$5$$$ gaps between adjacent elements and inserting separators there.
To make Condition A hold, it is necessary and sufficient to insert separators between $$$a_3$$$ and $$$a_4$$$, $$$a_5$$$ and $$$a_6$$$; thus the number of such partitions is $$$2^3=8$$$.
To make Condition B hold, it is necessary and sufficient to insert separators between $$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$; thus the number of such partitions is $$$2^3=8$$$.
To make both Condition A and Condition B hold, similarly we can obtain that the number of such partitions is $$$2$$$.
So, the answer is $$$8+8-2=14$$$.