// 那就是希望。
// 即便需要取模，也是光明。
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
    template<const ullt p>
    class mod_ullt
    {
        private:
            ullt v;
            inline ullt chg(ullt w){return(w<p)?w:w-p;}
            inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
        public:
            mod_ullt():v(0){}
            mod_ullt(ullt v):v(v%p){}
            bol empty(){return!v;}
            inline ullt val(){return v;}
            friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
            friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
            friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
            friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
            friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
            friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
            inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
            inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
            inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
            friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
            friend mod_ullt operator^(mod_ullt a,ullt b){return a._power(b);}
            inline mod_ullt operator-(){return _chg(p-v);}
            mod_ullt sqrt()
            {
                if(power(v,(p-1)>>1,p)!=1)return 0;
                mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
                ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
                mod_ullt x=_power((t+1)>>1),e=_power(t);
                while(k<s)
                {
                    if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                    e=_power(p-2)*x*x,k++;
                }
                return _min(x,-x),x;
            }
            mod_ullt inv(){return _power(p-2);}
            mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
            voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
            voi print()
            {
                static chr C[20];uint tp=0;
                ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
                while(tp--)putchar(C[tp]);
            }
            voi println(){print(),putchar('\n');}
            mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
        public:
            inline ullt&operator()(){return v;}
            inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
            inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
            inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
            mod_ullt&operator^=(ullt b){return*this=_power(b);}
            mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
            mod_ullt&operator++(){return v=chg(v+1),*this;}
    };
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
const ullt Mod=998244353;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
std::vector<uint>Way[200005];uint n,m;
voi dfs1(uint p,uint f)
{
    static uint S[100005],Dfn[100005],Dep[100005],F[100005],cnt=0;
    static std::vector<uint>A;
    if(!~f)for(auto&s:Dfn)s=-1;
    std::vector<uint>B;
    Dep[p]=A.size(),A.push_back(p),Dfn[p]=cnt++,F[p]=f;
    for(auto s:Way[p])if(~Dfn[s]){if(Dfn[s]<Dfn[p])S[A[Dep[s]+1]]--,S[p]++;}else B.push_back(s),dfs1(s,p),S[p]+=S[s];
    Way[p]=B,A.pop_back();
    if(!~f)
    {
        A.swap(B),m=n,Way[p].clear();
        while(A.size())
        {
            B={A.back()},A.pop_back(),Way[F[B[0]]].push_back(m),Way[m].push_back(F[B[0]]);
            while(B.size())
            {
                p=B.back(),B.pop_back();for(auto s:Way[p])(S[s]?B:A).push_back(s);
                Way[p]={m},Way[m].push_back(p);
            }
            m++;
        }
        // for(uint i=0;i<n;i++)
        // {
        //     for(auto s:Way[i])
        //         printf("%u ",s+1);
        //     puts("");
        // }
        // fflush(stdout);
    }
}
uint getwp(uint p,uint f,uint&wp)
{
    uint ans=p<n,t=0,user;
    for(auto s:Way[p])if(s!=f)_max(t,user=getwp(s,p,wp)),ans+=user;
    _max(t,n-ans);if(t*2<=n)wp=p;
    return ans;
}
std::vector<uint>Son[200005];uint Siz[200005];
voi dfs2(uint p,uint f)
{
    Siz[p]=p<n;for(auto s:Way[p])if(s!=f)dfs2(s,p),Siz[p]+=Siz[s],Son[p].push_back(s);
    std::sort(Son[p].begin(),Son[p].end(),[&](uint a,uint b){return Siz[a]<Siz[b];});
}
uint d,u;
using Beg = std::vector<std::pair<uint,modint> >;
modint solve(uint p)
{
    if(Siz[p]<d)return 0;
    if(p<n)
    {
        Beg B{{1,1}};
        for(auto s:Son[p])
        {
            if(B.empty())break;
            modint w=solve(s);
            if(w.empty())
            {
                for(auto&g:B)g.first+=Siz[s];
                while(B.size()&&B.back().first>u)B.pop_back();
                continue;
            }
            Beg A,T;
            for(auto&g:B)A.push_back({g.first,g.second*w}),g.first+=Siz[s];
            while(B.size()&&B.back().first>u)B.pop_back();
            if(B.empty()){B=A;continue;}
            for(uint i=0,j=0,p;i<A.size()||j<B.size();)
                p=std::min(i<A.size()?A[i].first:-1u,j<B.size()?B[j].first:-1u),
                T.push_back({p,(i<A.size()&&A[i].first==p?A[i++].second:0)+
                                    (j<B.size()&&B[j].first==p?B[j++].second:0)});
            B.clear();for(auto s:T)if(s.first<=u&&s.second())B.push_back(s);
        }
        modint w;
        for(auto&g:B)if(g.first>=d)w+=g.second;
        return w;
    }
    else
    {
        modint g(1);
        for(auto s:Son[p])
        {
            if(g.empty())break;
            g*=solve(s);
        }
        return g;
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint o,rot;scanf("%u%u%u",&n,&m,&o);
    while(m--){uint u,v;scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);}
    dfs1(0,-1),getwp(0,-1,rot=-1),dfs2(rot,-1);
    modint ans;
    if(o)
    {
        ans=-ans;
        std::vector<uint>T;
        for(uint i=2;i<=n;i=n/(n/i)+1)T.push_back(n/i);
        for(auto s:T)d=s,u=s+1,ans+=solve(rot);
        for(uint i=1;i<T.size();i++)if(T[i]+1==T[i-1]&&!(n%T[i-1]))d=u=T[i-1],ans-=solve(rot);
    }
    else for(uint i=1;i<n;i++)if(!(n%i))u=d=i,ans+=solve(rot);
    ans.println();
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。