vector<int> f() {
	vector<int> res;

	for(i = 1; i <= q; ++i) {
		memset(aux, 0, sizeof aux);

		++aux[x[i]][a[x[i]]];
		for(j = x[i] + 1; j <= y[i]; ++j) {
			++aux[j][a[j]];

			for(k = 0; k < m; ++k) {
				int to = (a[j] + k) % m;
				aux[j][to] = (aux[j][to] + aux[j - 1][k]) % MOD;
				aux[j][k] = (aux[j][k] + aux[j - 1][k]) % MOD;
			}
		}

		res.push_back((aux[y[i]][0] + 1) % MOD);
	}

	return res;
}