#include <bits/stdc++.h>
using namespace std;
#define SINGLE_TEST 1
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define REP(i, k, n) for (int(i) = (k); (i) <= (n); ++(i))
#define REPR(i, k, n) for (int(i) = (k); (i) >= (n); --(i))
#define FORR(x, arr) for (auto &x : arr)
#define FORR2(x, y, arr) for (auto &[x, y] : arr)
#define ALL(a) (a.begin()), (a.end())
#define RALL(a) (a.rbegin()), (a.rend())
#define REVERSE(v) reverse(ALL(v))
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << (x) << endl
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LLINF = 1e18;
void solve() {
int n; cin >> n;
vl d(n), x(n);
FOR(i, n) cin >> d[i] >> x[i];
vector<unordered_map<int, ll>> v(n);
vector<unordered_map<int, ll>> r(n);
vl ways(n);
ways[0] = 1;
ll ans = 0;
FOR(i, n) {
ans = (ans + ways[i]) % MOD;
if (x[i] && d[i]) {
v[i][d[i]] = (v[i][d[i]]+ways[i])%MOD;
ll e = i+d[i]*(x[i]+1);
if (e < (ll)n) {
v[e][d[i]] = (v[e][d[i]]-ways[i]+MOD)%MOD;
ways[e] = (ways[e]-ways[i]+MOD)%MOD;
}
}
FORR2(len, cnt, v[i]) if (cnt && i+len < n) {
v[i+len][len] = (v[i+len][len]+cnt)%MOD;
ways[i+len] = (ways[i+len]+cnt)%MOD;
}
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#if SINGLE_TEST
solve();
#else
int t;
cin >> t;
while (t--) {
solve();
}
#endif
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |