#include <bits/stdc++.h>

const int maxn = 18;
const int maxm = 1 << 18;
const int mod = 19260817;
int f[maxm][maxn][2],G[maxn][maxn],sum[maxm];
int n,k,c,ans;

int main() {
	freopen("GodFly.in","r",stdin);
	freopen("GodFly.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= k;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		-- u;
		-- v;
		++ G[u][v];
		++ G[v][u];
	}
	scanf("%d",&c);
	
	const int S = (1 << n);
	for(int i = 1;i < S;++ i) {
		for(int k = 0;k < n;++ k) {
			if(i >> k & 1)
				(sum[i] += (k + 1) & 1) &= 1; 
		}
	}
	
	int ans = 0;
	f[1][0][0] = 1;
	
	for(int i = 1;i < (1 << (n - 1));++ i) {
		if(!(i & 1))continue ;
		for(int k = 0;k < n - 1;++ k) {
			if(!(i >> k & 1))continue ;
			if(!f[i][k][0]&&!f[i][k][1])continue ;
			for(int j = 0;j < n;++ j) {
				if(i >> j & 1)continue ;
				if(!G[k][j])continue ;
				(f[i | (1 << j)][j][((j + 1) * sum[i]) & 1] += 1ll * G[k][j] * f[i][k][0] % mod) %= mod;
				(f[i | (1 << j)][j][(1 + (j + 1) * sum[i]) & 1] += 1ll * G[k][j] * f[i][k][1] % mod) %= mod;
			}
		}
	}
	
	for(int i = (1 << (n - 1));i < S;++ i)(ans += f[i][n - 1][c]) %= mod;
	printf("%d",ans);
	return 0;
}