Rust
When computing (a / b) % m in function Combination(a, b), we cannot treat it as a % m / (b % m), we can only apply % m to the final result, but overflow may hap
When computing `(a / b) % m` in function `Combination(a, b)`, we cannot treat it as `a % m / (b % m)`, we can only apply `% m` to the final result, but overflow may happen when multiplying.\nWe can use `mod inserse` to transform it into `a * mod_inverse(b) % m`, then apply `% m` anywhere as we want.\n\n```\nimpl Solution {\n    pub fn num_of_ways(nums: Vec<i32>) -> i32 {\n        Self::count(nums) as i32 - 1\n    }\n\n    fn count(nums: Vec<i32>) -> usize {\n        if nums.len() <= 2 {\n            return 1;\n        }\n\n        let mut left = vec![];\n        let mut right = vec![];\n        let root = nums[0];\n        for n in nums.into_iter().skip(1) {\n            if n > root {\n                right.push(n);\n            } else {\n                left.push(n);\n            }\n        }\n        let m = 1_000_000_007;\n        let mut ret = Self::foo(left.len(), right.len());\n        if ret == 0 {\n            ret = 1;\n        }\n        let left = Self::count(left);\n        let right = Self::count(right);\n        ret = ret * left % m * right % m;\n        ret\n    }\n\n    // for example:\n    // n is 2: [1, 2]\n    // m is 2: [3, 4]\n    // merge m array into a array, keep themselies order\n    // [3, 4, 1, 2], [1, 3, 4, 2], [1, 2, 3, 4]\n    // [3, 1, 4, 2], [3, 1, 2, 4], [1, 3, 2, 4]\n    fn foo(mut n: usize, mut m: usize) -> usize {\n        Self::C(n + m, n)\n    }\n\n    // Combination number, pick r from n\n    fn C(n: usize, r: usize) -> usize {\n        (1..=r.min(n - r)).fold(1, |acc, i| acc * (n - i + 1) % 1_000_000_007 * Self::mod_inverse(i) % 1_000_000_007)\n    }\n\n    // modular inverse, use Fermat\'s little theorem\n    // a^(M - 1) === 1 (mod M) => a^-1 === a^(M - 2) (mod M)\n    fn mod_inverse(mut a: usize) -> usize {\n        Self::power(a, 1_000_000_005)\n    }\n\n    // a ^ b % M\n    fn power(mut a: usize, mut b: usize) -> usize {\n        let mut ret = 1;\n        let m = 1_000_000_007;\n        while b > 0 {\n            if b & 1 == 1 {\n                ret = (ret * a) % m;\n            }\n            a = (a * a) % m;\n            b >>= 1;\n        }\n        ret\n    }\n}\n```
['Rust']