# **Đệ quy có nhớ**
## Enjoy cake
**O(6*n)**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const int M = 1e9 + 7;

long long n, ans;
long long f[N][2][3];

// void dp(int pos, int A, int B, int C) {
//     if(pos == n+1){
//         if(A%2 == 0&&B%3 ==0){
//             ans++;
//         }
//         return;
//     }
//     dp(pos+1,A+1,B,C);
//     dp(pos+1,A,B+1,C);
//     dp(pos+1,A,B,C+1);
// }

ll cal(ll pos, ll A, ll B) {
    // B1: Đặt trả về
    if (pos == n + 1) {
        if (A % 2 == 0 && B % 3 == 0) return 1; 
        return 0;
    }

    // B2: QHĐ:
    if (f[pos][A][B] != -1) return f[pos][A][B];

    // B3: Sinh những trạng thái tiếp theo
    ll tmp = 0;
    tmp += cal(pos + 1, (A + 1) % 2, B);
    tmp += cal(pos + 1, A, (B + 1) % 3);
    tmp += cal(pos + 1, A, B);
    tmp %= M;

    // B4: Lưu kết quả
    f[pos][A][B] = tmp;
    return tmp;   
}

// O(3^n)
// O(n^4)
// O(n^3)
// O(6 * n)

int main(){
    cin >> n;
    memset(f, -1, sizeof(f));
    cout << cal(1, 0, 0);
}

## Minh, Ngọc, Sam
**O(n*S^2/9)**

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const ll N=1e6+6, mod=1e9+7;
ll cnt, n;

void open(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

const int N = 100 + 1;
const int S = 20 * 100;
const ll M = 1e9 + 7;

ll n;
ll a[N], s[N], ans = 0;
ll f[N][S / 3 + 1][S / 3 + 1];

ll cal(ll pos, ll y, ll z) {
    if (pos == n + 1) {
        if (s[n] - y - z > y && y == z) return 1;
        return 0;
    }
    if (f[pos][y][z] != -1) return f[pos][y][z];

    ll tmp = 0;
    tmp += cal(pos + 1, y, z);
    if (y + a[pos] <= S / 3) tmp += cal(pos + 1, y + a[pos], z);
    if (z + a[pos] <= S / 3) tmp += cal(pos + 1, y, z + a[pos]);
    tmp %= M;

    f[pos][y][z] = tmp;
    return tmp;
}
// O(n * S^3 / 9)

void SOLVE() {
	cin >> n;
	for (int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    memset(f, -1, sizeof(f));
	cout << cal(1, 0, 0);
}

int main() {
	freopen("BAI3.inp","r",stdin);
	freopen("BAI3.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t--) SOLVE();
    return 0;
}