C++11(clang++ 3.9) 解法, 执行用时: 1634ms, 内存消耗: 3052K, 提交时间: 2018-04-01 11:19:32

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<assert.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long long ll;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int lim=161;
int u[110],v[110],op[110];
int f[1<<12][lim];
int sum[lim];
const int mod=1e9+7;
#define MOD mod
namespace linear_seq {
	const int LMAXN = 10010;
	ll res[LMAXN], base[LMAXN], _c[LMAXN], _md[LMAXN];
	vector<ll> Md;

	ll pw(ll a, ll b) {
		ll res = 1;
		a %= MOD;
		for(; b; b >>= 1) {
			if(b & 1) res = res * a % MOD;
			a = a * a % MOD;
		}
		return res;
	}

	void mul(ll *a, ll *b, ll k) {
		for(int i = 0; i < k + k; i++) _c[i] = 0;
		for(int i = 0; i < k; i++) if(a[i]) {
				for(int j = 0; j < k; j++) {
					_c[i + j] = (_c[i + j] + a[i] * b[j]) % MOD;
				}
			}
		for(int i = k + k - 1; i >= k; i--) if(_c[i]) {
				for(int j = 0; j < (int)Md.size(); j++) {
					_c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % MOD;
				}
			}
		for(int i = 0; i < k; i++) a[i] = _c[i];
	}

	ll solve(ll n, vector<ll> a, vector<ll> b) {
		ll ans = 0, pnt = 0;
		int k = a.size();
		for(int i = 0; i < k; i++) {
			_md[k - 1 - i] = -a[i];
		}
		_md[k] = 1;
		Md.clear();
		for(int i = 0; i < k; i++) if(_md[i]) {
				Md.push_back(i);
			}
		for(int i = 0; i < k; i++) res[i] = base[i] = 0;
		res[0] = 1;
		while((1LL << pnt) <= n) pnt++;
		for(int p = pnt; p >= 0; p--) {
			mul(res, res, k);
			if((n >> p) & 1) {
				for(int i = k - 1; i >= 0; i--) {
					res[i + 1] = res[i];
				}
				res[0] = 0;
				for(int j = 0; j < (int)Md.size(); j++) {
					res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % MOD;
				}
			}
		}
		for(int i = 0; i < k; i++) {
			ans = (ans + res[i] * b[i]) % MOD;
		}
		if(ans < 0) ans += MOD;
		return ans;
	}

	vector<ll> BM(vector<ll> s) {
		vector<ll> C(1, 1), B(1, 1);
		ll L = 0, m = 1, b = 1;
		for(int n = 0; n < (int)s.size(); n++) {
			ll d = 0;
			for(int i = 0; i < L + 1; i++) {
				d = (d + C[i] * s[n - i]) % MOD;
			}
			if(!d) ++m;
			else if(2 * L <= n) {
				vector<ll> T = C;
				ll c = MOD - d * pw(b, MOD - 2) % MOD;
				while(C.size() < B.size() + m) C.push_back(0);
				for(int i = 0; i < (int)B.size(); i++) {
					C[i + m] = (C[i + m] + c * B[i]) % MOD;
				}
				L = n + 1 - L; B = T; b = d; m = 1;
			} else {
				ll c = MOD - d * pw(b, MOD - 2) % MOD;
				while(C.size() < B.size() + m) C.push_back(0);
				for(int i = 0; i < (int)B.size(); i++) {
					C[i + m] = (C[i + m] + c * B[i]) % MOD;
				}
				++m;
			}
		}
		return C;
	}

	ll work(vector<ll> a, ll n) {
		vector<ll> c = BM(a);
		c.erase(c.begin());
		for(int i = 0; i < (int)c.size(); i++) {
			c[i] = (MOD - c[i]) % MOD;
		}
		return solve(n, c, vector<ll>(a.begin(), a.begin() + c.size()));
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
	int n,all,m,i,j,s,t,o,cur;char c;
	while (cin>>all>>n>>m) {
		for (s=0;s<1<<n;s++)
			for (i=0;i<lim;i++)
				f[s][i]=0;
		for (i=1;i<=m;i++) {
			cin>>u[i];u[i]--;
			while (1) {
				if ((c=getchar())=='=')
					op[i]=1;
				else if (c=='!') getchar(),op[i]=2;
				else
					if (c=='<')
						if (getchar()=='=') op[i]=3;
						else op[i]=5;
					else if (c=='>')
						if (getchar()=='=') op[i]=4;
						else op[i]=6;
					else continue;
				break;
			}
			cin>>v[i];v[i]--;
			if (op[i]==4) op[i]=3,swap(u[i],v[i]);
			if (op[i]==6) op[i]=5,swap(u[i],v[i]);
		}
		f[0][0]=1;
		for (s=0;(s+1)<1<<n;s++) {
			cur=n-__builtin_popcount(s);
			for (j=0;j<lim;j++) {
				sum[j]=f[s][j];
				if (j>=cur) (sum[j]+=sum[j-cur])%=mod;
			}
			for (o=t=((1<<n)-1)^s;t;(--t)&=o) {
				for (i=1;i<=m;i++) {
					if (op[i]==1&&(t>>u[i]&1)!=(t>>v[i]&1)) break;
					if (op[i]==2&&(t>>u[i]&1)&&(t>>v[i]&1)) break;
					if (op[i]==3&&(t>>u[i]&1)&&(s>>v[i]&1)) break;
					if (op[i]==3&&(t>>v[i]&1)&&!((s|t)>>u[i]&1)) break;
					if (op[i]==5&&(t>>u[i]&1)&&((s|t)>>v[i]&1)) break;
					if (op[i]==5&&(t>>v[i]&1)&&!(s>>u[i]&1)) break;
				}
				if (i>m)
					for (i=cur;i<lim;i++)
						(f[s|t][i]+=sum[i-cur])%=mod;
			}
		}
		vector<LL>v;
		for (i=1;i<lim;i++) v.pb(f[s][i]);
		printf("%lld\n",linear_seq::work(v,all-1));
	}
	
	return 0;
}