3183. The Number of Ways to Make the Sum

You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.

Given an integer n, return the number of ways to make the sum of n with the coins you have.

Since the answer may be very large, return it modulo 109 + 7.

Note that the order of the coins doesn’t matter and [2, 2, 3] is the same as [2, 3, 2].

long long mod = 1e9 + 7;
class Solution {
    long long helper(int n) {
        if(n == 0) return 1;
        if(n < 0) return 0;
        long long res = 0;
        while(n > 0) {
            res = (res + 1 + n / 2) % mod;
            n -= 6;
        }
        return res + (n == 0);
    }
public:
    int numberOfWays(int n) {
        return (helper(n) + helper(n-4) + helper(n-8)) % mod;
    }
};