Marton 的朋友 Cero 有一个由 \(N\) 个正整数组成的数组。
首先 Cero 会在黑板上写下这个数组中的第一个数字。接下来他会在之前写下的所有数的左边或者右边写下一个数字。重复以上操作得到一个序列。
请注意，根据上述方法构造出的两个序列相同当且仅当每一个数字写下的顺序完全相同。例如，\(1,1\) 可能和 \(1,1\) 不同，前者的第二个数在第一个数的左边，后者的第二个数在第一个数的右边。
求这些数组成的所有序列中，最长严格递增子序列长度的最大值 \(M\)，以及所有最长严格递增子序列长度等于 \(M\) 的序列中，最长严格递增子序列个数的总和。考虑到答案可能很大，Marton 只想知道这个数对 \(10^9+7\) 取模的值。
链接
求出以每个元素为x开头的LIS和LDS的长度，相加即是第一问。
除了最长上升子序列之外的数都可以从任意方向加入