#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
const ll p = 1e9+7;
const ll i2 = 5e8+4;
ll e2(ll x) {
x %= (p-1);
if (x==0) {
return 1;
} else if (x==1) {
return 2;
} else if (x%2==0) {
ll y = e2(x/2);
return (y*y)%p;
} else {
ll y = e2(x/2);
return (2*y*y)%p;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
/*freopen("io.txt","r",stdin);
freopen("out.txt","w",stdout);*/
ll N,M,K; cin >> N >> M >> K;
if (K==0) {
cout << (e2(N)+e2(M)-2)%p; exit(0);
}
ll pt = -1; ll ans = 0;
map<ll,ll> px,py;
for (ll k=0;k<K;k++) {
string s; ll x,y; cin >> s >> x >> y;
x--; y--;
ll vpt,vpx,vpy;
if (s=="+") {
vpt = (x+y)%2;
vpx = x%2;
vpy = y%2;
} else {
vpt = (x+y+1)%2;
vpx = (x+1)%2;
vpy = (y+1)%2;
}
if (pt==-1) {
pt=vpt;
} else if (pt != vpt) {
pt=-2;
}
if (py.find(y)==py.end()) {
py[y]=vpx;
} else if (py[y]!=vpx) {
py[y]=-1;
}
if (px.find(x)==px.end()) {
px[x]=vpy;
} else if (px[x]!=vpy) {
px[x]=-1;
}
}
if (pt==-1) {
ans += (p-2);
} else if (pt==0 || pt==1) {
ans += (p-1);
}
ll ax = e2(N); ll ay = e2(M);
for (pii p0: px) {
if (p0.second==-1) {
ax = 0;
} else {
ax = (ax*i2)%p;
}
}
for (pii p0: py) {
if (p0.second==-1) {
ay = 0;
} else {
ay = (ay*i2)%p;
}
}
ans = (ans+ax+ay)%p;
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
456 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
456 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
41 ms |
1332 KB |
Output is correct |
17 |
Correct |
42 ms |
1332 KB |
Output is correct |
18 |
Correct |
41 ms |
1372 KB |
Output is correct |
19 |
Correct |
32 ms |
1448 KB |
Output is correct |
20 |
Correct |
32 ms |
1360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
456 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
41 ms |
1332 KB |
Output is correct |
17 |
Correct |
42 ms |
1332 KB |
Output is correct |
18 |
Correct |
41 ms |
1372 KB |
Output is correct |
19 |
Correct |
32 ms |
1448 KB |
Output is correct |
20 |
Correct |
32 ms |
1360 KB |
Output is correct |
21 |
Correct |
88 ms |
9044 KB |
Output is correct |
22 |
Correct |
0 ms |
352 KB |
Output is correct |
23 |
Correct |
87 ms |
9128 KB |
Output is correct |
24 |
Correct |
86 ms |
9048 KB |
Output is correct |
25 |
Correct |
86 ms |
9044 KB |
Output is correct |
26 |
Correct |
83 ms |
12596 KB |
Output is correct |
27 |
Correct |
82 ms |
12620 KB |
Output is correct |
28 |
Correct |
82 ms |
12532 KB |
Output is correct |
29 |
Correct |
87 ms |
12628 KB |
Output is correct |
30 |
Correct |
101 ms |
14932 KB |
Output is correct |