class Solution {
    int mod = (int)(1e9) + 7;
    
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        long res = 1;

        while(n > 4){
            n -= 3;
            res = (res * 3) % mod;
        }

        res = (res * n) % mod;
        return (int) res;
    }
}