C solution
Code\n\n#define MOD 1000000007\nlong long dfs(int *nums, int numsSize, int **combination_table)\n{\n  if(numsSize<3)\n    return 1;\n  int *large = (int*)malloc
# Code\n```\n#define MOD 1000000007\nlong long dfs(int *nums, int numsSize, int **combination_table)\n{\n  if(numsSize<3)\n    return 1;\n  int *large = (int*)malloc(sizeof(int)*10000);\n  int *small = (int*)malloc(sizeof(int)*10000);\n  int lidx=0, sidx=0;\n  for(int i=1;i<numsSize;i++)\n  {\n    if(nums[i]>nums[0])\n      large[lidx++] = nums[i];\n    else\n      small[sidx++] = nums[i];\n  }\n  large = realloc(large, sizeof(int)*lidx);\n  small = realloc(small, sizeof(int)*sidx);\n  long long largeway = dfs(large, lidx, combination_table)%MOD;\n  long long smallway = dfs(small, sidx, combination_table)%MOD;\n\n  return ((largeway*smallway)%MOD)*(combination_table[numsSize-1][lidx])%MOD;\n}\n\n\nint numOfWays(int* nums, int numsSize){\n  int i, j;\n\n  int **combination_table = (int**)malloc(sizeof(int*)*numsSize);\n  for(i=0;i<numsSize;i++)\n    combination_table[i] = (int*)malloc(sizeof(int)*numsSize);\n  \n  for(i=0;i<numsSize;i++)\n  {\n    for(j=0;j<=i;j++)\n    {\n      if(j==0 || i==j)\n        combination_table[i][j] = 1;\n      else\n        combination_table[i][j] = (combination_table[i-1][j] + combination_table[i-1][j-1])%MOD;\n    }\n  }\n\n  return (dfs(nums, numsSize, combination_table)-1)%MOD;\n}\n```
['C']