#include <bits/stdc++.h>
#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;
const int M=1e9+7;
map<pii,int>mp;
int n,m;
bool check(int x,int y){
// cerr<<"ALO "<<endl;
for(int dx=-1;dx<1;dx++){
for(int dy=-1;dy<1;dy++){
// cout<<dx<<' '<<dy<<endl;
int sx=x+dx,sy=y+dy;
if(sx<=0 || sy<=0 || sx>=n || sy>=m) continue;
vec<int>c(2,0);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
if(mp.count({sx+i,sy+j})) c[mp[{sx+i,sy+j}]]++;
}
}
// cout<<"NE"<<<<' '<endl;
if(c[0]>2 || c[1]>2){
return 0;
}
}
// cout<<dx<<endl;
}
return 1;
}
int mult(int a,int b){
return 1ll*a*b%M;
}
int binpow(int a,int b){
int ans=1;
// cout<<b<<endl;
while(b){
if(b&1) ans=mult(ans,a);
b>>=1;a=mult(a,a);
}
return ans;
}
void paint(map<int,int> &gp,int x,int v){
if(gp.count(x)){
if(gp[x]!=v){
cout<<0;
exit(0);
}
}
gp[x]=v;
}
signed main(){
fast_ioi;
int k;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
char c;int x,y;
cin>>c>>x>>y;
swap(x,y);
int w=(c=='+'?1:0);
mp[{x,y}]=w;
}
int ok=1;
vec<pii>mm;
for(auto &z : mp) mm.pb(z.f);
for(auto &z : mm) ok&=check(z.f,z.s);
// for(auto &z : mp) cerr<<z.f.f<<' '<<z.f.s<<' '<<z.s<<endl;
map<int,int>mpx,mpy,xs,ys;
// auto paint=[&](i)
for(auto &z : mm){
// pii z=q.f;
xs[z.f]++;ys[z.s]++;
if(mp.count({z.f,z.s+1}) && mp[{z.f,z.s+1}]==mp[{z.f,z.s}]) {
int c=((z.f)%2)^mp[{z.f,z.s}];
// cerr<<c<<endl;
paint(mpy,z.s,c);
paint(mpy,z.s+1,c);
}
// cerr<<mp.count({z.f+1,z.s})<<' '<<z.f<<' '<<z.s<<endl;
if(mp.count({z.f+1,z.s}) && mp[{z.f+1,z.s}]==mp[{z.f,z.s}]){
int c=((z.s)%2)^mp[{z.f,z.s}];
paint(mpx,z.f,c);
paint(mpx,z.f+1,c);
}
}
for(auto &z : mm){
if(mpx.count(z.f)){
int c=((z.s)%2)^mp[{z.f,z.s}];
paint(mpx,z.f,c);
}
if(mpy.count(z.s)){
int c=((z.f)%2)^mp[{z.f,z.s}];
paint(mpy,z.s,c);
}
}
// cout<<sz(mpx)<<' '<<sz(mpy)<<' '<<ok<<endl;
if((sz(mpx) && sz(mpy)) || !ok){
cout<<0;
return 0;
}
if(sz(mpx)){
cout<<binpow(2,m-sz(mpx));
}
else if(sz(mpy)){
cout<<binpow(2,n-sz(mpy));
}
else{
cout<<binpow(2,n+m-sz(xs)-sz(ys));
}
return 0;
}
/*
7 3
0
1
0
1
3
5
0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
