矩阵快速幂用的是之前写的模板，应该没写错，已经用它ac了几道别的题。

#include <iostream>
#include <string>
using namespace std;
size_t n,m,v,a,b,t,ans;
template<typename IS>
class Matrix{
protected:
    IS *p=new IS;
    unsigned long long cm=1,cn=1,tom=1,ton=1;
    IS (*usuall)(const Matrix&,unsigned long long,unsigned long long)=standard;
    static IS standard(const Matrix& input,unsigned long long a,unsigned long long b){if(input.colunm()&&input.row()) return input[a%input.colunm()][b%input.row()];else return 0;}
public:
    Matrix(unsigned long long inm=0,unsigned long long inn=0,initializer_list<initializer_list<IS>> input={{0}}){
        (*this)(inm,inn);
        for(IS* i=(*this).begin();i<(*this).end();i++) (*i)=0;
        (*this)=input;
    }
    Matrix(const initializer_list<initializer_list<IS>> &input){
        unsigned long long big=0;
        for(initializer_list<IS> i:input)
            if(big<i.size()) big=i.size();
        (*this)(input.size(),big);
        for(IS* i=(*this).begin();i<(*this).end();i++) (*i)=0;
        (*this)=input;
    }
    Matrix(const Matrix& a){(*this)=a;}
    Matrix(Matrix&& a){
        (*this).p=a.p;
        a.p=NULL;
        (*this).cm=(*this).tom=a.cm;
        (*this).cn=(*this).ton=a.cn;
        (*this).usuall=a.usuall;
    }
    ~Matrix(){delete p;};
    void getdata(IS(*getdata)(const Matrix&,unsigned long long,unsigned long long)=standard){usuall=getdata;}
    IS* begin() const{return p;}
    IS* end() const{return p+cm*cn;}
    unsigned long long size() const{return cm*cn;}
    friend ostream& operator << (ostream& os,const Matrix &a){
        for(unsigned long long i=0;i<a.colunm();i++){
            for(unsigned long long j=0;j<a.row();j++)
                os<<a[i][j]<<' ';
            if(i!=a.colunm()-1) os<<'\n';
        }
        return os;
    }
    void operator=(const Matrix &a){
        if(&a==this) return;
        (*this)(a.colunm(),a.row());
        for(unsigned long long i=0;i<cm;i++)
            for(unsigned long long j=0;j<cn;j++)
                (*this)[i][j]=a[i][j];
    }
    void operator=(const initializer_list<initializer_list<IS>> &a){
        unsigned long long cnt1=0,cnt2;
        for(auto i:a){
            if(cnt1>=cm) break;
            cnt2=0;
            for(auto j:i){
                if(cnt2>=cn) break;
                (*this)[cnt1][cnt2]=j;
                cnt2++;
            }
            cnt1++;
        }
    }
    void operator()(unsigned long long inm=0,unsigned long long inn=0){
        if(inm==cm&&inn==cn) return;
        IS *q=new IS[inm*inn];
        tom=inm;
        ton=inn;
        for(unsigned long long i=0;i<inm;i++)
            for(unsigned long long j=0;j<inn;j++)
                *(q+i*ton+j)=(*usuall)((*this),i,j);
        delete p;
        p=q;
        cm=inm;
        cn=inn;
    }
    unsigned long long colunm() const{return cm;}
    unsigned long long to_colunm() const{return tom;}
    unsigned long long row() const{return cn;}
    unsigned long long to_row() const{return ton;}
    IS* operator[](unsigned long long inm) const{
        if(inm>tom||inm<0) return NULL;
        return p+inm*cn;
    }
    bool operator>(const Matrix &a) const{
        bool ans=1;
        unsigned long long sm=cm<a.colunm()?cm:colunm(),sn=cn<a.row()?cn:a.row();
        for(unsigned long long i=0;i<sm;i++)
            for(unsigned long long j=0;j<sn;j++)
                if((*this)[i][j]<=a[i][j]) ans=0;
        return ans;
    }
    bool operator<(const Matrix &a) const{
        bool ans=1;
        unsigned long long sm=cm<a.colunm()?cm:colunm(),sn=cn<a.row()?cn:a.row();
        for(unsigned long long i=0;i<sm;i++)
            for(unsigned long long j=0;j<sn;j++)
                if((*this)[i][j]>=a[i][j]) ans=0;
        return ans;
    }
    bool operator>=(const Matrix &a) const{
        bool ans=1;
        unsigned long long sm=cm<a.colunm()?cm:colunm(),sn=cn<a.row()?cn:a.row();
        for(unsigned long long i=0;i<sm;i++)
            for(unsigned long long j=0;j<sn;j++)
                if((*this)[i][j]<a[i][j]) ans=0;
        return ans;
    }
    bool operator<=(const Matrix &a) const{
        bool ans=1;
        unsigned long long sm=cm<a.colunm()?cm:colunm(),sn=cn<a.row()?cn:a.row();
        for(unsigned long long i=0;i<sm;i++)
            for(unsigned long long j=0;j<sn;j++)
                if((*this)[i][j]>a[i][j]) ans=0;
        return ans;
    }
    void Standard_matrix(){
        IS small=cm<cn?cm:cn;
        (*this)(small,small);
        for(unsigned long long i=0;i<cm;i++)
            for(unsigned long long j=0;j<cn;j++)
                (*this)[i][j]=(i==j?1:0);
    }
    const Matrix operator+() const{return *this;}
    Matrix operator+(Matrix adder) const{
        IS inm=adder.colunm()<cm?adder.colunm():cm,inn=adder.row()<cn?adder.row():cn;
        Matrix inp,ans(inm,inn);
        inp=(*this);
        adder(inm,inn);
        inp(inm,inn);
        for(unsigned long long i=0;i<inm;i++)
            for(unsigned long long j=0;j<inn;j++)
                ans[i][j]=inp[i][j]+adder[i][j];
        return ans;
    }
    void operator+=(const Matrix &adder){(*this)=adder+(*this);}
    const Matrix& operator++(){
        for(IS* i=(*this).begin();i<(*this).end();i++) (*i)++;
        return (*this);
    }
    const Matrix operator++(int){
        Matrix old;
        old=*this;
        ++(*this);
        return old;
    }
    const Matrix operator-() const{
        Matrix ans(*this);
        for(IS* i=ans.begin();i<ans.end();i++) *i=-*i;
        return ans;
    }
    Matrix operator-(Matrix small) const{
        IS inm=small.colunm()<cm?small.colunm():cm,inn=small.row()<cn?small.row():cn;
        Matrix inp,ans(inm,inn);
        inp=(*this);
        small(inm,inn);
        inp(inm,inn);
        for(unsigned long long i=0;i<inm;i++)
            for(unsigned long long j=0;j<inn;j++)
                ans[i][j]=inp[i][j]-small[i][j];
        return ans;
    }
    void operator-=(const Matrix &small){(*this)=(*this)-small;}
    Matrix& operator--(){
        for(IS* i=(*this).begin();i<(*this).end();i++) (*i)--;
        return (*this);
    }
    const Matrix operator--(int){
        Matrix old;
        old=*this;
        --(*this);
        return old;
    }
    Matrix operator*(IS a) const{
        Matrix ans(cm,cn);
        for(unsigned long long i=0;i<cm;i++)
            for(unsigned long long j=0;j<cn;j++)
                ans[i][j]=(*this)[i][j]*a;
        return ans;
    }
    Matrix operator*(Matrix a) const{
        IS small=cn<a.colunm()?cn:a.colunm();
        Matrix inp,ans(cm,a.row());
        inp=(*this);
        inp(cm,small);
        a(small,a.row());
        for(unsigned long long i=0;i<cm;i++){
            for(unsigned long long j=0;j<a.row();j++){
                ans[i][j]=0;
                for(unsigned long long l=0;l<small;l++)
                    (ans[i][j]+=inp[i][l]*a[l][j]%m)%=m;
            }
        }
        return ans;
    }
    template<typename IN>
    friend Matrix<IN> operator*(IN a,Matrix<IN> input){ return input*a;}
    void operator*=(IS a){(*this)=(*this)*a;}
    void operator*=(const Matrix &a){*this=*this*a;}
    operator string() const{
        string ans="";
        for(unsigned long long i=0;i<cm;i++){
            for(unsigned long long j=0;j<cn;j++)
                ans+=ulltos((*this)[i][j])+' ';
            if(i!=cm-1) ans+='\n';
        }
        return ans;
    }
    template<typename NUM>
    operator NUM() const{
        NUM ans=0;
        for(unsigned long long i=0;i<cm;i++)
            for(unsigned long long j=0;j<cn;j++)
                ans+=(*this)[i][j];
        ans/=cm*cn;
        return ans;
    }
    template<typename NUM>
    Matrix<NUM> to() const{
        Matrix<NUM> ans(cm,cn);
        for(unsigned long long i=0;i<cm;i++)
            for(unsigned long long j=0;j<cn;j++)
                ans[i][j]=(NUM)((*this)[i][j]);
        return ans;
    }
    Matrix rotate(unsigned long long time=1){
        Matrix replace;
        replace=(*this);
        time--;
        time%=4;
        for(int i=0;i<=time;i++){
            Matrix ans(replace.row(),replace.colunm());
            for(unsigned long long i=0;i<replace.colunm();i++)
                for(unsigned long long j=0;j<replace.row();j++)
                    ans[j][replace.row()-i-1]=replace[i][j];
            replace(ans.colunm(),ans.row());
            for(unsigned long long i=0;i<replace.colunm();i++)
                for(unsigned long long j=0;j<replace.row();j++)
                    replace[i][j]=ans[i][j];
        }
        return replace;
    }
    Matrix pow(unsigned long long time=2){
        unsigned long long size=cn<cm?cn:cm;
        Matrix mid1,mid2(size,size);
        mid1=(*this);
        mid1(size,size);
        mid2.Standard_matrix();
        while(time){
            if(time&1) mid2*=mid1;
            mid1*=mid1;
            time>>=1;
        }
        return mid2;
    }
};
Matrix<size_t> dp;
int main(){
    m=2017;
    cin>>n>>v;
    dp(n+1,n+1);
    for(size_t i=0;i<=n;i++)
        dp[i][0]=dp[i][i]=1;
    for(size_t i=1;i<=v;i++){
        cin>>a>>b;
        dp[a][b]=dp[b][a]=1;
    }
    cin>>t;
    dp=dp.pow(t);
    for(size_t i=0;i<=n;i++)
        (ans+=dp[1][i])%m;
    cout<<ans<<endl;
    return 0;
}