• 21

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

Sheldon gives Leonard a collection of arrays V, where each item V_i is an array of variable length. His task is to merge V into a sorted array, knowing that the final array S will contain n distinct integers in the range [1,n]. Sadly, the final array S is only partially sorted. As Leonard is new to programming he wrote a very basic algorithm in pseudocode:
S = []
m = V.size()
while not V.empty()
U = []
for i = 1; i <= m; i = i + 1
if not V[i].empty()
x = V[i][0]
V[i].remove(x)
U.push(x)
while not U.empty()
x = min(U)
U.remove(x)
S.push(x)
return S

Example
Let V = { [3, 2], [5], [4, 1] }.
U and S are the unsorted and sorted array respectively.

Step 1:
V = { [2], [], [1] }
U = { 3, 5, 4 }
S = { 3, 4, 5 }

Step 2:
V = { [], [] }
U = { 2, 1 }
S = { 3, 4, 5, 1, 2 }

Leonard ran Sheldon's input collection V through his algorithm to get the resulting sorted array S. Unfortunately, Sheldon forgot the initial contents of V. You must help Sheldon reverse-engineer the contents of S to get the initial contents of V.

Task: You are given the sorted array S and you have to find the number of different ways to re-create the initial collection V such that it produces S when given as input to Leonard's algorithm. This number can be very large, so print it modulo 10^7 + 7.

Sample 1:

Input 1:
4
1 2 4 3

Output 1:
6

Explanation 1:

There are six distinct possible results:

V = { [1, 2, 4, 3] }
V = { [1, 4, 3], [2] }
V = { [1, 3], [2], [4] }
V = { [1], [2, 4, 3] }
V = { [1], [2], [4, 3] }
V = { [1], [2, 3], [4] }

As such, we print the result of 6 mod (10^7 + 7) = 6 as the final answer.

Sample 2:

Input 2:
5
5 4 3 2 1

Output 2:
1

Explanation 2:

There is only one possible result:

V = { [5, 4, 3, 2, 1] }

As such, we print the result of 1 mod (10^7 + 7) = 1 as the final answer.
Input
Line 1: An integer n, denoting the size of array S.
Line 2: n space-separated integers representing the values held by S.
Output
An integer denoting the number of different ways to re-create collection V, modulo 10^7 + 7.
Constraints
1 ≤ n ≤ 1500
1 ≤ Sin
Every array V_i from the initial collection of arrays V must be a non-empty array
Example
Input
4
1 2 4 3
Output
6

A higher resolution is required to access the IDE