#include <iostream>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll i2 = (mod + 1) / 2ll, i3 = (mod + 1) / 3ll;
ll fI(ll x, ll y){
ll mn = min(x, y);
ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod + mn + 1ll) % mod;
if(x > y){
ll p1 = ((mod - 3ll) * (x + y + 1ll) % mod + 2ll + y) % mod;
p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (y + 1ll)) % mod;
rs = (rs + tp) % mod;
}else{
ll p1 = ((mod - 1ll) * (x + y + 1ll) % mod + 2ll + mod - x) % mod;
p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
p2 = (mod - p2) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (x + 1ll)) % mod;
rs = (rs + tp) % mod;
}
return rs;
}
ll fII(ll x, ll y){
x *= -1ll;
ll mn = min(x, y);
ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
(rs += (2ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
rs = (rs + mn * (mn + 1ll) % mod + mn + 1ll) % mod;
if(x > y){
ll p1 = ((1ll) * (x + y + 1ll) % mod + 2ll + mod - y) % mod;
p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (y + 1ll)) % mod;
rs = (rs + tp) % mod;
}else{
ll p1 = ((mod - 1ll) * (x + y + 1ll) % mod + 2ll + x) % mod;
p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
p2 = (mod - p2) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (x + 1ll)) % mod;
rs = (rs + tp) % mod;
}
return rs;
}
ll fIII(ll x, ll y){
x *= -1ll; y *= -1ll;
ll mn = min(x, y);
ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
(rs += (4ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
rs = (rs + (2ll * mn + 1ll) * 1ll * (mn + 1ll) % mod) % mod;
if(x > y){
ll p1 = ((1ll) * (x + y + 1ll) % mod + 2ll + y) % mod;
p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (y + 1ll)) % mod;
rs = (rs + tp) % mod;
}else{
ll p1 = ((3ll) * (x + y + 1ll) % mod + 2ll + mod - x) % mod;
p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
p2 = (mod - p2) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (x + 1ll)) % mod;
rs = (rs + tp) % mod;
}
return rs;
}
ll fIV(ll x, ll y){
y *= -1ll;
ll mn = min(x, y);
ll rs = (2ll * mn * mn % mod * (mn + 1ll) % mod * (mn + 1ll) % mod) % mod;
(rs += (2ll * mn * (mn + 1ll) % mod * (2ll * mn + 1ll) % mod) * i3 % mod) %= mod;
rs = (rs + (mn + 1ll) * 1ll * (3ll * mn + 1ll) % mod) % mod;
if(x > y){
ll p1 = ((mod - 3ll) * (x + y + 1ll) % mod + 2ll + mod - y) % mod;
p1 = (p1 * 1ll * (x - y)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (y + 1ll)) % mod;
rs = (rs + tp) % mod;
}else{
ll p1 = ((3ll) * (x + y + 1ll) % mod + 2ll + x) % mod;
p1 = (p1 * 1ll * (y - x)) % mod; p1 = (p1 * 1ll * i2) % mod;
ll p2 = 2ll * x % mod * (x + 1ll) % mod * (2ll * x + 1ll) % mod;
p2 = (p2 + ((mod - 2ll) * y % mod * (y + 1ll) % mod * (2ll * y + 1ll)) % mod) % mod;
p2 = (p2 * i3) % mod;
p2 = (mod - p2) % mod;
ll tp = (p1 + p2) % mod;
tp = (tp * (x + 1ll)) % mod;
rs = (rs + tp) % mod;
}
return rs;
}
ll rsI(ll x1, ll x2, ll y1, ll y2){
if(x1 > x2 || y1 > y2) return 0ll;
ll ans = fI(x2, y2);
if(x1) ans = (ans + mod - fI(x1 - 1, y2)) % mod;
if(y1) ans = (ans + mod - fI(x2, y1 - 1)) % mod;
if(x1 && y1) ans = (ans + fI(x1 - 1, y1 - 1)) % mod;
return ans;
}
ll rsII(ll x1, ll x2, ll y1, ll y2){
if(x1 > x2 || y1 > y2) return 0ll;
ll ans = fII(x1, y2);
if(x2) ans = (ans + mod - fII(x2 + 1ll, y2)) % mod;
if(y1) ans = (ans + mod - fII(x1, y1 - 1ll)) % mod;
if(x2 && y1) ans = (ans + fII(x2 + 1ll, y1 - 1ll)) % mod;
return ans;
}
ll rsIII(ll x1, ll x2, ll y1, ll y2){
if(x1 > x2 || y1 > y2) return 0ll;
ll ans = fIII(x1, y1);
if(x2) ans = (ans + mod - fIII(x2 + 1ll, y1)) % mod;
if(y2) ans = (ans + mod - fIII(x1, y2 + 1ll)) % mod;
if(x2 && y2) ans = (ans + fIII(x2 + 1ll, y2 + 1ll)) % mod;
return ans;
}
ll rsIV(ll x1, ll x2, ll y1, ll y2){
if(x1 > x2 || y1 > y2) return 0ll;
ll ans = fIV(x2, y1);
if(x1) ans = (ans + mod - fIV(x1 - 1ll, y1)) % mod;
if(y2) ans = (ans + mod - fIV(x2, y2 + 1ll)) % mod;
if(x1 && y2) ans = (ans + fIV(x1 - 1ll, y2 + 1ll)) % mod;
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
for(ll x1, y1, x2, y2; q --;){
cin >> x1 >> y1 >> x2 >> y2;
ll ansI = rsI(max(x1, 0ll), min(x2, 1000000000ll), max(y1, 0ll), min(y2, 1000000000ll));
ll ansII = rsII(max(x1, -1000000000ll), min(x2, -1ll), max(y1, 0ll), min(y2, 1000000000ll));
ll ansIII = rsIII(max(x1, -1000000000ll), min(x2, -1ll), max(y1, -1000000000ll), min(y2, -1ll));
ll ansIV = rsIV(max(x1, 0ll), min(x2, 1000000000ll), max(y1, -1000000000ll), min(y2, -1ll));
ll ans = (ansI + ansII) % mod;
ans = (ans + ansIII) % mod;
ans = (ans + ansIV) % mod;
cout << ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
