Java || 7ms || DFS with Pascal's Triangle
\nclass Solution {\n    // Pascal\'s Triangle is built only once per SUBMIT, and then can be \n    // used for all other test cases of the SUBMIT.\n    private 
```\nclass Solution {\n    // Pascal\'s Triangle is built only once per SUBMIT, and then can be \n    // used for all other test cases of the SUBMIT.\n    private static int[][] pascalsTriangle = createPascalsTriangle(1001);\n    private static final int MOD = 1_000_000_007;\n\n    \n    // Main method called by leetcode.\n    public int numOfWays(int[] nums) {\n        return dfs(nums, nums.length) - 1;\n    }\n\n    \n    // Use an array representing a root followed by the values below that root, \n    // to calculate the number of combinations, by recursively breaking the \n    // array into smaller tree problems.\n    private int dfs(int[] nums, int n) {\n        if (n <= 2)  return 1;\n        final int[] left = new int[n - 1];\n        final int[] right = new int[n - 1];\n        final int rootVal = nums[0];\n        int leftIdx = 0;\n        int rightIdx = 0;\n        for (int i = 1; i < n; i++) \n            if (nums[i] < rootVal) \n                left[leftIdx++] = nums[i];\n            else\n                right[rightIdx++] = nums[i];\n        return (int)(((((long)dfs(left, leftIdx) * dfs(right, rightIdx)) % MOD) * \n                pascalsTriangle[n - 1][leftIdx]) % MOD);\n    }\n    \n    \n    // Build table of Pascal\'s triangle values.  Only have to build \n    // it once per SUBMIT, then all test cases can use the same triangle.\n    static private int[][] createPascalsTriangle(int maxN) {\n        int[][] pt = new int[maxN][];\n        for (int i = 0; i < maxN; i++) {\n            pt[i] = new int[i + 1];\n            pt[i][0] = pt[i][i] = 1;\n            for (int j = 1; j < i; j++) \n                pt[i][j] = (pt[i - 1][j - 1] + pt[i - 1][j]) % MOD;\n        }\n        return pt;\n    }\n}\n```\n\n**--- Update: June 20, 2023 ---**\nSomeone has some code that runs at 4ms and uses a different algorithm.  My code ran at 7ms.  I like this faster code.  It still uses the trick of creating a fixed value table only once per SUBMIT, then the other test cases can use that generated table.  This code show a different and better method for initializing a fixed value table called `mults[]`, from the method used in the above code for `pascalsTriangle[][]`.\n```\nclass Solution {\n    static final int MAX = 1000;\n\tstatic final int MOD = 1_000_000_007;\n\tstatic final TreeNode[] q = new TreeNode[MAX];\n\tstatic final long[] mults = new long[MAX + 1];\n\tstatic {\n\t\tmults[0] = 1;\n\t\tfor (int i = 1; i <= MAX; i++) \n\t\t\tmults[i] = (mults[i - 1] * i) % MOD;\n\t}\n\n\tpublic int numOfWays(int[] nums) {\n\t\tTreeNode root = new TreeNode(nums[0]);\n\t\tfor (int i = 1; i < nums.length; i++) {\n\t\t\troot.add(nums[i]);\n\t\t}\n\t\tint len = 0;\n\t\tq[len++] = root;\n\t\tlong d = 1;\n\t\tfor (int i = 0; i < len; i++) {\n\t\t\tfinal TreeNode node = q[i];\n\t\t\td = (d * node.count) % MOD;\n\t\t\tif (node.left != null)\n\t\t\t\tq[len++] = node.left;\n\t\t\tif (node.right != null)\n\t\t\t\tq[len++] = node.right;\n\t\t}\n\t\treturn (int) ((mults[len] * inverse(d) + MOD - 1) % MOD);\n\t}\n\n\tstatic long inverse(long y) {\n\t\tlong e = MOD - 2, a = 1;\n\t\twhile (e > 0) {\n\t\t\tif (e % 2 == 1) {\n\t\t\t\ta = (a * y) % MOD;\n\t\t\t}\n\t\t\te /= 2;\n\t\t\ty = (y * y) % MOD;\n\t\t}\n\t\treturn a;\n\t}\n\t\n\tstatic final class TreeNode {\n\t\tint val;\n\t\tint count;\n\n\t\tTreeNode left;\n\t\tTreeNode right;\n\n\t\tpublic TreeNode(int val) {\n\t\t\tthis.val = val;\n\t\t\tthis.count = 1;\n\t\t}\n\n\t\tvoid add(int val) {\n\t\t\tfor (TreeNode node = this;;) {\n\t\t\t\tnode.count++;\n\t\t\t\tfinal TreeNode next = val < node.val ? node.left : node.right;\n\t\t\t\tif (next == null) {\n\t\t\t\t\tif (val < node.val) {\n\t\t\t\t\t\tnode.left = new TreeNode(val);\n\t\t\t\t\t} else {\n\t\t\t\t\t\tnode.right = new TreeNode(val);\n\t\t\t\t\t}\n\t\t\t\t\tbreak;\n\t\t\t\t} else {\n\t\t\t\t\tnode = next;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n}\n```
['Java']