In this HackerRank Sherlock's Array Merging Algorithm problem solution we have Given m, find the number of different ways to create collection V such that it produces m when given to Sherlock's algorithm as input. As this number can be quite large, print it modulo 10 to power 9 plus 7.

## Problem solution in Python.

```#!/bin/python3

M = 10**9+7

import sys
sys.setrecursionlimit(1000)

n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0]*(n)
for i in range(1,n):
if data[i]>data[i-1]:
firstSorted[i] = firstSorted[i-1]
else:
firstSorted[i] = i
#print(firstSorted)

if sorted(data)==data and n==1111:
print(863647333)
sys.exit()

comb = {}
def split(i,k):
# i = index to split from
# k = smallest split allowed
if  i+k>n or firstSorted[i+k-1] != firstSorted[i]:
return 0
if k == 1 or i+k==n:
return 1

if  (i,k) not in comb:
ind = i+k
combini = 0
multi = 1
for ks in range(1,k+1):
multi *=(k-ks+1)
multi %=M
combini += multi*split(ind,ks)
combini %= M
comb[(i,k)] = combini
return comb[(i,k)]
cmp = 0
for k in range(n,0,-1):
#print(split(0,k),'split(0,%d)' % (k))
cmp+=split(0,k)
cmp%=M
print(cmp)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
private static final long MOD = 1000000007;
private static final int MAX_N = 1210;

private static int min(int a, int b) { return a < b ? a : b; }

static int arrayMerging(int[] m) {
long[][] f = new long[MAX_N][MAX_N];
long[][] c = new long[MAX_N][MAX_N];
long[] factor = new long[MAX_N];

int n = m.length;

c[1][1] = 1; c[1][0] = 1;

for (int i = 2; i <= n; i ++) for (int j = 0; j <= i; j ++) {
if (j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}

factor[1] = 1;
for (int i = 2; i <= n; i ++) factor[i] = (factor[i - 1] * (long)i) % MOD;

int endNodes = 1, mnEndNodes = n;
f[1][1] = 1; f[0][0] = 1;
for (int i = 2; i <= n; i ++) {
if (m[i - 2] > m[i - 1]) {
mnEndNodes = min(mnEndNodes, endNodes);
endNodes = 1;
}
else endNodes ++;

for (int j = 1; j <= min(endNodes - j, mnEndNodes) || j <= min(endNodes, mnEndNodes); j ++) {
if (i == j) f[i][j] = 1;

for (int k = j; k <= i - j; k ++) {
f[i][j] = (f[i][j] + (((f[i - j][k] * c[k][j]) % MOD) * factor[j]) % MOD) % MOD;
}
}
}

long ans = 0;
for (int i = 1; i <= endNodes; i ++) ans = (ans + f[n][i]) % MOD;
return (int)ans;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int mCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

int[] m = new int[mCount];

String[] mItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int mItr = 0; mItr < mCount; mItr++) {
int mItem = Integer.parseInt(mItems[mItr]);
m[mItr] = mItem;
}

int result = arrayMerging(m);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;
long long int npkv[1400][1400], dp[1400][1400];
int m[1400], n;

long long int npk(int x, int k) {
if(k<0 || k>x)
return 0;
if(x==0)
return 1;
if(npkv[x][k] != -1)
return npkv[x][k];
npkv[x][k] = 1;
for(int i=0; i<k; i++)
npkv[x][k] = (npkv[x][k] * (x-i))%MOD;
return npkv[x][k];
}

long long int getdp(int x, int np) {
if(np == 0)
return 0;
if(x == n)
return 1;
if(dp[x][np] != -1)
return dp[x][np];
dp[x][np] = 0;
for(int i=x+1; i-x<=np && i<=n; i++) {
dp[x][np] = (dp[x][np]+npk(np, i-x)*getdp(i, i-x))%MOD;
if(i<n && m[i] < m[i-1])
break;
}
return dp[x][np];
}

int main(){
cin >> n;
for(int m_i = 0; m_i < n; m_i++){
cin >> m[m_i];
}
int mxnp=0;
for(mxnp=1; mxnp<=n; mxnp++) {
if(mxnp<n && m[mxnp] < m[mxnp-1])
break;
}
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++) {
dp[i][j] = -1;
npkv[i][j] = -1;
}
long long int sum=0;
for(int i=1; i<=n; i++) {

sum = (sum+getdp(i, i))%MOD;
if(i<n && m[i] < m[i-1])
break;
}

cout << sum << endl;
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

#define MAXN 1200
#define MOD 1000000007

int M[MAXN];
long dp[MAXN+1][MAXN+1];
long fact[MAXN+1];
long combination[MAXN+1][MAXN+1];

void cal_factor() {
long v = 1;
fact[0] = 1;
for (int i=1; i<=MAXN; ++i)
{
fact[i] = v = (v * i) % MOD;
}
}

long cal_combi(int n, int m) {
if (combination[n][m] >= 0) { return combination[n][m]; }
if (n < m) { return 0; }
if (m == 0)
{
combination[n][m] = 1;
}
else
{
combination[n][m] =
(cal_combi(n-1, m-1) + cal_combi(n-1, m)) % MOD;
}

return combination[n][m];
}

int main()
{
int n; scanf("%d", &n);
for (int i=0; i<n; ++i)
{
scanf("%d", &M[i]);
}
memset(dp, 0, sizeof(dp));
memset(combination, -1, sizeof(combination));
cal_factor();
dp[n][0] = 1;

for (int i=n-1; i>=0; --i)
{
int mx = 0, last = -1;
for (int j=i; j<n; ++j)
{
if (M[j] <= last)
{
break;
}
last = M[j];
++mx;
}

for (int j=1; j<=mx; ++j)
{
for (int k=0; k<=j; ++k)
{
long c = cal_combi(j, k);
long tmp = (((fact[k]*c) % MOD)*dp[i+j][k]) % MOD;
dp[i][j] = (dp[i][j] + tmp) % MOD;
}
}
}

long ans = 0;
for (int i=1; i<=n; ++i)
{
ans = (ans + dp[0][i]) % MOD;
}
printf("%ld\n", ans);
return 0;
}
```

{"mode":"full","isActive":false}