#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1'000'007;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int nums; cin >> nums;
vector<int> vec(nums + 1), pmax(nums + 1, 0);
for (int i = 1; i <= nums; i++) {
cin >> vec[i];
pmax[i] = max(pmax[i - 1], vec[i]);
}
vector<vector<ll>> memo(2, vector<ll>(nums + 1, 0));
bool prev = 0;
for (int i = 1; i < nums; i++) memo[0][i] = 1;
int ans = 0;
for (int i = nums; i >= 1; i--) {
ans += (memo[prev][pmax[i - 1]] * (vec[i] - 1)) % mod;
ans %= mod;
for (int j = 1; j < i; j++) memo[1 - prev][j] = (j * memo[prev][j] + memo[prev][j + 1]) % mod;
prev = 1 - prev;
}
cout << (ans + 1) % mod;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
280 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
464 KB |
Output is correct |
2 |
Correct |
23 ms |
460 KB |
Output is correct |
3 |
Correct |
23 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
608 KB |
Output is correct |
2 |
Correct |
96 ms |
588 KB |
Output is correct |
3 |
Correct |
84 ms |
588 KB |
Output is correct |