Video Solution | Java C++ Python
\n\n\n\n\n\n\n\n\nclass Solution {\n    long mod = (long)1e9 + 7;\n    long[][] table;\n    public int numOfWays(int[] nums) {\n        int n = nums.length;\n  
\n\n\n\n<iframe width="560" height="315" src="https://www.youtube.com/embed/N8MDBYhF4dM" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n\n\n```\nclass Solution {\n    long mod = (long)1e9 + 7;\n    long[][] table;\n    public int numOfWays(int[] nums) {\n        int n = nums.length;\n        table = new long[n][n];\n        for (int i = 0; i < n; ++i) {\n            table[i][0] = table[i][i] = 1;\n        }\n        for (int i = 2; i < n; i++) {\n            for (int j = 1; j < i; j++) {\n                table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;\n            }\n        }\n        List<Integer> arrList = new ArrayList();\n        for(int i: nums) arrList.add(i);\n        return (int)((helper(arrList) - 1) % mod);\n        \n    }\n    \n    public long helper(List<Integer> arr){\n        int n = arr.size();\n        if(n<3) return 1;\n        List<Integer> leftNodes = new ArrayList<>();\n        List<Integer> rightNodes = new ArrayList<>();\n        for (int i  = 1; i<n;i++) {\n            int element = arr.get(i);\n            if (element < arr.get(0)) {\n                leftNodes.add(element);\n            } else {\n                rightNodes.add(element);\n            }\n        }\n        long leftWays = helper(leftNodes)%mod;\n        long rightWays = helper(rightNodes) % mod;\n        return (((leftWays * rightWays) % mod) * table[n - 1][leftNodes.size()]) % mod;\n    }\n}\n```\n\n```\n\n\nclass Solution {\n    long long mod = 1000000007;\n    std::vector<std::vector<long long>> table;\n    \npublic:\n    int numOfWays(std::vector<int>& nums) {\n        int n = nums.size();\n        table.resize(n, std::vector<long long>(n));\n        \n        for (int i = 0; i < n; ++i) {\n            table[i][0] = table[i][i] = 1;\n        }\n        \n        for (int i = 2; i < n; i++) {\n            for (int j = 1; j < i; j++) {\n                table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;\n            }\n        }\n        \n        std::vector<int> arrList;\n        for (int i : nums)\n            arrList.push_back(i);\n            \n        return (int)((helper(arrList) - 1) % mod);\n    }\n    \n    long long helper(std::vector<int>& arr) {\n        int n = arr.size();\n        if (n < 3)\n            return 1;\n            \n        std::vector<int> leftNodes;\n        std::vector<int> rightNodes;\n        \n        for (int i = 1; i < n; i++) {\n            int element = arr[i];\n            if (element < arr[0]) {\n                leftNodes.push_back(element);\n            } else {\n                rightNodes.push_back(element);\n            }\n        }\n        \n        long long leftWays = helper(leftNodes) % mod;\n        long long rightWays = helper(rightNodes) % mod;\n        \n        return (((leftWays * rightWays) % mod) * table[n - 1][leftNodes.size()]) % mod;\n    }\n};\n\n```\n\n```\nclass Solution:\n    mod = 10**9 + 7\n    table = []\n\n    def numOfWays(self, nums):\n        n = len(nums)\n        self.table = [[0] * n for _ in range(n)]\n\n        for i in range(n):\n            self.table[i][0] = self.table[i][i] = 1\n\n        for i in range(2, n):\n            for j in range(1, i):\n                self.table[i][j] = (self.table[i - 1][j - 1] + self.table[i - 1][j]) % self.mod\n\n        arrList = nums\n        return (self.helper(arrList) - 1) % self.mod\n\n    def helper(self, arr):\n        n = len(arr)\n        if n < 3:\n            return 1\n\n        leftNodes = []\n        rightNodes = []\n        for i in range(1, n):\n            element = arr[i]\n            if element < arr[0]:\n                leftNodes.append(element)\n            else:\n                rightNodes.append(element)\n\n        leftWays = self.helper(leftNodes) % self.mod\n        rightWays = self.helper(rightNodes) % self.mod\n\n        return (((leftWays * rightWays) % self.mod) * self.table[n - 1][len(leftNodes)]) % self.mod\n\n```
['C', 'Python', 'Java']