#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

inline ll pw(ll a,ll b,ll mod)
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1) ans=(ans*base)%mod;
		base=(base*base)%mod; b>>=1;
	}
	return ans;
}

ll a,b,c;

int main()
{
	cin>>a>>b>>c;
	ll tmp=pw(b,c,4); tmp+=4;
	ll ans=pw(a,tmp,10);
	cout<<ans<<endl;
	return 0;
}
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=59;

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,m,col[N],res=0,ans=1;
bool vst[N];
bool ed[N][N];
vector<int>e[N],vec;

void dfs(int u,int ret=0) {
	vst[u]=1;
	vec.push_back(u);
	for(auto v:e[u]) if(!vst[v]) dfs(v);
}
void sfd(int pos) {
	if(pos==vec.size()) {
		res++;
		return;
	}
	rep(i,1,3) {
		bool qwq=1;
		rep(j,0,pos-1) if(ed[vec[pos]][vec[j]]&&col[j]==i) qwq=0;
		if(!qwq) continue;
		col[pos]=i;
		sfd(pos+1);
	}
}

signed main() {
	n=read(), m=read();
	rep(i,1,m) {
		int u=read(), v=read();
		e[u].push_back(v), e[v].push_back(u);
		ed[u][v]=ed[v][u]=1;
	}
	rep(i,1,n) if(!vst[i]) {
		vec.clear(), res=0;
		dfs(i);
		sfd(0);
		ans*=res;
	}
	printf("%lld\n",ans);
	return 0;
}