Practice Dynamic programming and Optimization with the exercise "Big Bang Theory

Learning Opportunities

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

Statement

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 ≤ Si ≤ n
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

Solve it

A higher resolution is required to access the IDE