#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;
ll power(ll a,ll b){
	ll ans = 1;
	while(b>0){
		if(b&1){
			ans = (ans*a)%MOD;
		}
		
		a = (a*a)%MOD;
		b>>=1;
	}
	return ans;
}
int main() {
    ll n ;
    ll m;
    ll k;
    cin>>n>>m>>k;
    
    vector<ll>G[n+1];
    
    for(int i = 1 ; i<=m ;i++){
    	int u,v;
    	cin>>u>>v;
    	G[u].push_back(v);
    	G[v].push_back(u);
    }
    int red=0 , blue = 0;
    vector<int>used(n+1);
    queue<ll>q;
    used[1]=1;
    q.push(1);red++;
    bool ans = true;
  
    //int k = n*m -count;
    while(!q.empty()){
    	auto u = q.front();
    	q.pop();
    	
    	for(auto v : G[u]){
    		if(used[v] == 0){
    			if(used[u] == 1){
    			used[v]=3;
    	
    			blue++;
    		}else if(used[u] == 3){
    				used[v] = 1;
    				red++;
    		}
    		q.push(v);
    	}else{
    	  if(used[u]+used[v] != 4){
    		ans = false;
    	}	
    	}}
    	
    	
    }
    
    ll t2 = k/3;
    ll t1  = k - t2;
    
   if (ans == false){
   	cout<<"no";
   }else{
   	cout<<red <<" "<<blue<<endl;
   	 cout<< ((1LL*power(t2,red)*power(t1,blue))%MOD+(1LL*power(t1,red)*power(t2,blue))%MOD)%MOD;
   }
	return 0;
}