Identify the time complexity of the following code as constant, linear, quadratic, cubic, log(n), nlog(n) or NP-hard. import java.io.*;
import java.util.*;

public class B {

	static int n, t[], g[], MOD = (int) 1e9 + 7;
	static int[][][] memo1, memo2[], memo3[];

	static int dp1(int idx, int remCnt, int remSum) {
		if (idx == n)
			return remSum == 0 && remCnt==0 ? 1 : 0;
		if (memo1[idx][remCnt][remSum] != -1)
			return memo1[idx][remCnt][remSum];
		int ans = dp1(idx + 1, remCnt, remSum);
		if (g[idx] == 0 && t[idx] <= remSum && remCnt>0) {
			ans += dp1(idx + 1, remCnt - 1, remSum - t[idx]);
			if (ans >= MOD)
				ans -= MOD;
		}
		return memo1[idx][remCnt][remSum] = ans;
	}

	static int dp2(int idx, int remCnt1, int remCnt2, int remSum) {
		int all = remCnt1 + remCnt2;
		if (all == 0)
			return remSum == 0 ? 1 : 0;
		if (idx == n || remSum == 0)
			return 0;
		if (memo2[idx][remCnt1][remCnt2][remSum] != -1)
			return memo2[idx][remCnt1][remCnt2][remSum];
		int ans = dp2(idx + 1, remCnt1, remCnt2, remSum);
		if (t[idx] <= remSum) {
			if (g[idx] == 1 && remCnt1 > 0)
				ans += dp2(idx + 1, remCnt1 - 1, remCnt2, remSum - t[idx]);
			else if (g[idx] == 2 && remCnt2 > 0)
				ans += dp2(idx + 1, remCnt1, remCnt2 - 1, remSum - t[idx]);

		}

		return memo2[idx][remCnt1][remCnt2][remSum] = ans;
	}

	private static int dp3(int cnt0, int cnt1, int cnt2, int last) {
		if (cnt0 + cnt1 + cnt2 == 0)
			return 1;
		if (memo3[last][cnt0][cnt1][cnt2] != -1)
			return memo3[last][cnt0][cnt1][cnt2];
		long ans = 0;
		if (cnt0 > 0 && last != 0)
			ans += dp3(cnt0 - 1, cnt1, cnt2, 0);
		if (cnt1 > 0 && last != 1)
			ans += dp3(cnt0, cnt1 - 1, cnt2, 1);
		if (cnt2 > 0 && last != 2)
			ans += dp3(cnt0, cnt1, cnt2 - 1, 2);
		return memo3[last][cnt0][cnt1][cnt2] = (int) (ans % MOD);

	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		n = sc.nextInt();
		int[] fac = new int[n + 1];
		t = new int[n];
		g = new int[n];
		int[] cnt = new int[3];
		fac[0] = 1;
		for (int i = 1; i <= n; i++)
			fac[i] = (int) (i * 1L * fac[i - 1] % MOD);
		int T =... Complexity: