#include <algorithm>
#include <iostream>
typedef long long int ll;
int main() {
ll s, n;
std::cin >> s >> n;
ll v[n + 1];
ll w[n + 1];
ll k[n + 1];
for (ll i = 1; i <= n; i++) {
std::cin >> v[i] >> w[i] >> k[i];
}
ll dp[n + 1][s + 1];
for (ll i = 0; i <= n; i++) {
for (ll j = 0; j <= s; j++) {
dp[i][j] = 0;
}
}
for (ll i = 1; i <= n; i++) {
for (ll j = w[i]; j <= s; j++) {
for (ll m = 0; m <= k[i] && j - m * w[i] >= 0; m++) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - m * w[i]] + m * v[i]);
dp[i][j] %= (ll)(1e9 + 7);
}
}
}
std::cout << dp[n][s] << '\n';
}
