#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=19260817;
ll n,k;
ll g[30][30];
ll c;
ll sum;
ll ans;
ll mark[30];
void dfs(ll x,ll u,ll w)//x:点，u:方案数，w:体力 
{
	if(x==n)
	{
		if(w==c) ans=(ans+u)%p;
		return;
	}
	for(int q=1;q<=n;q++)
	{
		if(mark[q]==0)
		{
			mark[q]=1;sum+=x;
			dfs(q,u*g[x][q]%p,(w+q*sum)%2);
			mark[q]=0;sum-=x;
		}
	}
}
int main(){
	freopen("GodFly.in","r",stdin);
	freopen("GodFly.out","w",stdout);
cin>>n>>k;
for(int q=1;q<=k;q++)
{
	ll x,y;
	cin>>x>>y;
	g[x][y]++,g[y][x]++;
}
cin>>c;
mark[1]=1;
dfs(1,1,0);
cout<<ans;
return 0;
}