Language: C++

#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

template<int mod>
struct modulo {
	int w;
	operator int&() { return w; }
	operator int() const { return w; }
	
	modulo() {}
	modulo(int w, bool f = 0) { this->w = w; if (f) fix(); }
	void inline fix() { w %= mod; if (w < 0) w += mod; }
	modulo inline fix(int w) const { w %= mod; if (w < 0) w += mod; return w; }
	
	inline modulo  operator - () { w = -w + mod; return *this; }
	inline modulo& operator += (const modulo &b) { if ((w += b.w) >= mod) w -= mod; return *this; }
	inline modulo& operator -= (const modulo &b) { if ((w -= b.w) < 0) w += mod; return *this; }
	inline modulo& operator *= (const modulo &b) { w = (num) w * b.w % mod; return *this; }
	inline modulo& operator /= (const modulo &b) { w = (num) w * b.inv() % mod; return *this; }
	inline modulo  operator +  (const modulo &b) { modulo r = *this; r += b; return r; }
	inline modulo  operator -  (const modulo &b) { modulo r = *this; r -= b; return r; }
	inline modulo  operator *  (const modulo &b) { modulo r = *this; r *= b; return r; }
	inline modulo  operator /  (const modulo &b) { modulo r = *this; r /= b; return r; }
	
	modulo inline inv() const {
		int a = w, m = mod, u = 0, v = 1, t;
		for (; a != 0; t = m / a, m -= t * a, swap(a, m), u -= t * v, swap(u, v));
		return fix(u);
	}
	
	modulo inline pow(int p) const {
		if (!w)  return 0;
		modulo a = *this, r = 1;
		for (; p > 0; a *= a, p >>= 1) if (p & 1) r *= a;
		return r;
	}
};
const int mod = int(1000000007);
typedef modulo<mod> rem;

const int nsz = 20, msksz = (1 << nsz) - 1;
int n, m, k, full, g[nsz + 5][nsz + 5], lg[msksz + 5];
rem dp[nsz + 5][nsz + 5][msksz + 5], ans;

int inline lowbit(int S) { return S & -S; }

int inline at(int S, int id) { return S >> id & 1; }

int inline chg(int S, int id, int w) { return S + ((w - at(S, id)) << id); } 

string inline bin(int S) {
	string s;
	loop (i, n) s += at(S, i) + '0';
	return s;
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> k >> m;
	full = (1 << n) - 1;
	memset(g, -1, sizeof(g));
	cont (i, m) {
		int id, lvl, d;
		cin >> id >> lvl >> d;
		--id, --lvl;
		g[id][lvl] = d;
	}
	loop (i, n) lg[1 << i] = i;
	dp[0][0][0] = 1;
	loop (i, k) {
		// cerr << i << " -> " << i + 1 << ln;
		loop (j, n) {
			circ (S, 0, full) {
				rem val = dp[i][j][S];
				if (!val) continue;
				// cerr << i << ' ' << j << " (" << g[i][j] << ") " << ' ' << bin(S) << ": " << val << ln;
				if (j == n - 1) dp[i + 1][0][S] += val;
				if (j == n - 1) continue;
				if (at(S, j) == 0) {
					if (g[i][j] == 0 || g[i][j] == -1) {
						// cerr << " -> " << i << ' ' << j + 1 << ' ' << bin(S) << ln;
						dp[i][j + 1][S] += val;
					}
					if (g[i][j] == 1 || g[i][j] == -1) {
						int T = S & (full ^ ((1 << j) - 1));
						int to = lg[lowbit(T)];
						int nS = chg(to > j ? chg(S, to, 0) : S, j, 1);
						// cerr << bin(T) << ' ' << to << ln;
						// cerr << bin(S) << " => " << bin(to > j ? chg(S, to, 0) : S) << ' ' << bin(nS) << ln;
						// cerr << " -> " << i << ' ' << j + 1 << ' ' << bin(nS) << ln;
						dp[i][j + 1][nS] += val;
					}
				} else {
					if (g[i][j] == 1 || g[i][j] == -1) {
						// cerr << " -> " << i << ' ' << j + 1 << ' ' << bin(S) << ln;
						dp[i][j + 1][S] += val;
					}
				}
				// cerr << ln;
			}
		}
	}
	circ (S, 0, full) {
		ans += dp[k - 1][n - 1][S];
	}
	cout << ans << ln;
}

Compiler output:
/tmp/cc4vm9Jb.o: in function `main':
a.cc:(.text+0x5e6): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc4vm9Jb.o
a.cc:(.text+0x604): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc4vm9Jb.o
/tmp/cc4vm9Jb.o: in function `__static_initialization_and_destruction_0()':
a.cc:(.text+0x6aa): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/cc4vm9Jb.o
collect2: error: ld returned 1 exit status