#include<cstdio>
#include<iostream>
using namespace std;
int n,k,x,y,_;
int head[20],ne[100010],v[100010],tot;
int done[20];
int hua,dui,f;
int add(int a,int b)
{
    v[++tot]=b;
    ne[tot]=head[a];
    head[a]=tot;
}
void dfs(int a,int w,int va)  
{
    if(done[a]) return;
    done[a]=1;
    if(a==n)
    {
        if((w+a*va)%2==1) dui=(dui+1)%19260817;
        else hua=(hua+1)%19260817;
        return;
    }
    for(int p=head[a];p;p=ne[p])
    {
        if(done[v[p]]) continue;
        dfs(v[p],(w+a*va)%2,va+a);    
        done[v[p]]=0;
    }     
    return;
}
int main()
{
    freopen("GodFly.in","r",stdin);
    freopen("GodFly.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0,0);
    scanf("%d",&_);
    if(_) printf("%d\n",dui);
    else printf("%d\n",hua);
    return 0;
}