//30pts #include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define m_p make_pair #define pi pair<int,int> #define p1 first #define p2 second using namespace std; typedef long long ll; const int N=55,mod=1e9+9; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,q,t,F[N][N],fa[N],ct,res,ans,ct2; stack<int>S; vector<ll>Q; struct MAT { int a[30][30],n,m; MAT(){ memset(a,0,sizeof(a)); } }T,pw[70]; MAT operator*(MAT a,MAT b){ MAT c;c.n=a.n,c.m=b.m; up(i,0,a.n)up(k,0,a.m)up(j,0,b.m)(c.a[i][j]+=a.a[i][k]*1ll*b.a[k][j]%mod)%=mod; return c; } int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int find(int x){ if(x==fa[x])return x; return find(fa[x]); } bool mg(int x,int y){ x=find(x),y=find(y); if(x==y)return 0; S.push(x);ct--; fa[x]=y;return 1; } void DFS(int x,int y,int s){ if(ct==1){ (res+=s)%=mod;return; }if(y>n)x++,y=x+1; if(x==n)return; if(mg(x,y)){ DFS(x,y+1,s*F[x][y]%mod); ct++; int x=S.top();S.pop(); fa[x]=x; } DFS(x,y+1,s); } ll calc(){ ct=n,res=0; up(i,1,n)fa[i]=i; DFS(1,2,1); return res; } void dfs(int x){ if(x>t){ ct2++;(ans+=calc())%=mod; return; } up(i,1,n)up(j,i+1,n){ (F[i][j]+=1)%=3; dfs(x+1); (F[i][j]+=2)%=3; } } void slv1(){ map<int,int>mp; for(ll x:Q){ if(!mp.count(x)){ t=x,ans=0,ct2=0;dfs(1); mp[x]=ans*1ll*qpow(ct2,mod-2)%mod; } printf("%d\n",mp[x]); } } int cal(int S){ int a=S%3;S/=3; int b=S%3;S/=3; int c=S%3;S/=3; ll res=0; if(a&&b)res+=a*b; if(a&&c)res+=a*c; if(b&&c)res+=b*c; return res; } void slv2(){ if(n==2){ for(ll x:Q){ ll res=(F[1][2]+x%3)%3; printf("%lld\n",res); }return; }T.n=26,T.m=26; up(i,0,26){ up(j,0,26){ if(i==j){ T.a[i][j]=0;continue; } vector<pair<int,pi> >qwq; int ii=i,jj=j; up(k,0,2){ if(ii%3!=jj%3)qwq.p_b(m_p(k,m_p(ii%3,jj%3))); ii/=3,jj/=3; } if(qwq.size()!=1){ T.a[i][j]=0;continue; }int x=qwq[0].p2.p1,y=qwq[0].p2.p2; if((x+1)%3!=y){ T.a[i][j]=0;continue; }T.a[i][j]=2*qpow(n*1ll*(n-1)%mod,mod-2)%mod; } } MAT tt; tt.n=0,tt.m=26; up(i,0,tt.m)tt.a[0][i]=0; int bs=F[1][2]*9+F[1][3]*3+F[2][3]; tt.a[0][bs]=1; pw[0]=T; up(i,1,60)pw[i]=pw[i-1]*pw[i-1]; for(ll x:Q){ if(!x){ printf("%d\n",cal(bs)); continue; } MAT ss=tt; up(i,0,60)if((x>>i)&1)ss=ss*pw[i]; ll res=0; up(i,0,26)(res+=ss.a[0][i]*1ll*cal(i)%mod)%=mod; printf("%d\n",res); } } void slv(){ n=read(),m=read(),q=read(); up(i,1,m){ int x=read(),y=read(); if(x>y)swap(x,y); F[x][y]=read(); } while(q--)Q.p_b(read()); ll mx=0; for(ll x:Q)mx=max(mx,x); if(mx<=5)slv1(); else slv2(); }int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }