1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>

const int M = 1'000'000'007;

class Solution {
public:
    int numberOfWays(int n) {
        if (n < 4) {
            return g(n);
        }
        if (n < 8) {
            return (g(n) + g(n - 4)) % M;
        }
        return ((g(n) + g(n - 4)) % M + g(n - 8)) % M;
    }
    
    int g(int n) {
        long long k = n / 6;
        long long res = (k + 1) * (2 * (n / 2) - 3 * k + 2) / 2;
        return res % M;
    }

    /*
    int f(int n) {
        return n / 2 + 1;
    }
    
    int g(int n) {
        int k = n / 6;
        int sum = 0;
        for (int i = 0; i <= k; ++i) {
            sum = (sum + f(n - i * 6)) % M;
        }
        return sum;
    }
    
    int h(int n) {
        if (n < 4) {
            return g(n);
        }
        if (n < 8) {
            return (g(n) + g(n - 4)) % M;
        }
        return ((g(n) + g(n - 4)) % M + g(n - 8)) % M;
    }
    */
};
};