# Big Bang Theory - Sheldon's Array Puzzle

Difficulty : Hard

Community success rate: 45%

Approved by an anonymous CodinGamer an anonymous CodinGamer an anonymous CodinGamer

A higher resolution is required to access the IDE

- 20

## 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 notV.empty()

U= []

for i = 1; i <=m; i = i + 1

if notV[i].empty()

x =V[i][0]

V[i].remove(x)

U.push(x)

while notU.empty()

x = min(U)

U.remove(x)

S.push(x)

returnS

**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 ≤

1 ≤

Every array

`n`≤ 15001 ≤

`Si`≤`n`Every array

**V_i**from the initial collection of arrays**V**must be a non-empty arrayExample

Input

4 1 2 4 3

Output

6

A higher resolution is required to access the IDE