Combination formula : C(m,n) = C(m-1,n) + C(m-1,n-1). Pre compute
C(m,n) = C(m-1,n) + C(m-1,n-1)\nC(m,n) represents the formula for combinations.\n\n\npublic class Solution\n{\n    long mod = (long)Math.Pow(10, 9) + 7;\n    pu
C(m,n) = C(m-1,n) + C(m-1,n-1)\nC(m,n) represents the formula for combinations.\n\n```\npublic class Solution\n{\n    long mod = (long)Math.Pow(10, 9) + 7;\n    public int NumOfWays(int[] nums)\n    {\n        int n = nums.Length;\n        long[,] dp = new long[n, n];\n        for (int i = 0; i < n; i++)\n        {\n            dp[i, 0] = 1;\n            for (int j = 1; j <= i; j++)\n            {\n                dp[i, j] = (dp[i - 1, j - 1] + dp[i - 1, j]) % mod;\n            }\n        }\n        return (int)Helper(nums, dp) - 1;\n    }\n\n    private long Helper(IList<int> nums, long[,] dp)\n    {\n        if (nums.Count < 2) return 1;\n        var left = nums.Where(x => x < nums[0]).ToList();\n        var right = nums.Where(x => x > nums[0]).ToList();\n\n        long res = dp[nums.Count - 1, left.Count] % mod;\n        res = res * Helper(left, dp) % mod;\n        res = res * Helper(right, dp) % mod;\n\n        return res;\n    }\n}\n```
[]