Quadratic Quest

#include <iostream>

using namespace std;

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

int dp[N][N];

int main() {
	int n, m;
	cin >> n >> m;

	for(int i = 1; i <= m; ++i) {
		dp[1][i] = 1;
	}

	for(int i = 2; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			//Calculate dp[i][j];

			int k = 1;
			while(j + k*k <= m) {
				dp[i][j] += dp[i-1][j + k*k];
				if(dp[i][j] >= M) dp[i][j] -= M;
				++k;
			}
			k = 0;
			while(j - k*k >= 1) {
				dp[i][j] += dp[i-1][j - k*k];
				if(dp[i][j] >= M) dp[i][j] -= M;
				++k;
			}
		}
	}

	int s = 0;
	for(int j = 1; j <= m; ++j) {
		s += dp[n][j];
		if(s >= M) s -= M;
	}
	cout << s << "\n";



}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED