• 20

## 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]      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], , [4, 1] }.
U and S are the unsorted and sorted array respectively.

Step 1:
V = { , [],  }
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],  }
V = { [1, 3], ,  }
V = { , [2, 4, 3] }
V = { , , [4, 3] }
V = { , [2, 3],  }

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