#include <bits/stdc++.h>
using namespace std;
//ofstream cout("output.out");

#define fast() {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define pb push_back
#define vi vector<int>
#define vl vector<ll>					
#define vii vector<vector<int>>
#define mii map<int, int>
#define pii pair<int, int>
#define qii priority_que<int, vector<int>, greater<int>>				
#define For(i, n) for(int i = 0; i < n; ++i)
#define For1(i, n) for(int i = 1; i <= n; ++i)
#define Forlr(i, l, r) for(int i = l; i <= r; ++i)
#define Forrl(i, r, l) for(int i = r; i >= l; --i)
#define o(a) { cout << #a << ":" << (a) <<" ";}
#define ov(a) {For(i, a.size()) cout << a[i] <<" ";}
#define ovv(a) {For(i, a.size()) {For(j, a[i].size()) cout << a[i][j] <<" ";cout <<"\n";}}
using ll = long long;
int n, m, k, q;
const int INF = 1e9 + 5;
const int nax = 1e5 + 5;
const ll mod = 1e9 + 7;	
const int maxn = 3e5 + 7;

int main()
{
	fast();
	cin >> n;
	vi a(n);
	For(i, n) cin >> a[i];
	unordered_map<int, int> g;
	For(i, n){
		for(int j = 1; j * j <= a[i]; ++j){
			if(a[i] % j == 0){
				g[j] = __gcd(a[i], g[j]);
				g[a[i] / j] = __gcd(a[i], g[a[i] / j]);
			}
		}
	}
	int mi = *min_element(a.begin(), a.end());
	int rs = 1;
	for(auto i : g){
		if(i.first == i.second && i.first < mi) rs++;
	}
	cout << rs <<"\n";
}
#include<bits/stdc++.h>
template <typename _Tp>void read(_Tp &x){
	char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
	if(f)x=-x;
}
template <typename _Tp,typename... Args>void read(_Tp &t,Args &...args){read(t);read(args...);}
const int N=105,mod=1000000007,inv2=(mod+1)/2;
typedef long long ll;
template<typename _Tp1,typename _Tp2>inline void add(_Tp1 &a,_Tp2 b){(a+=b)>=mod&&(a-=mod);}
template<typename _Tp1,typename _Tp2>inline void sub(_Tp1 &a,_Tp2 b){(a-=b)<0&&(a+=mod);}
ll ksm(ll a,ll b=mod-2){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}return res;}
int a[N],b[N];
int X[N*N],Y[N*N],n;
struct mat{
	int a[N][N];
	mat operator * (const mat &o)const{
		mat c;memset(c.a,0,sizeof(c.a));
		for(int i=0;i<n;++i)for(int k=0;k<n;++k)for(int j=0;j<n;++j)add(c.a[i][j],1ULL*a[i][k]*o.a[k][j]%mod);
		return c;
	}
}I,M,orig;
mat ksm(mat a,int b){
	mat res=I;
	while(b){
		if(b&1)res=res*a;
		a=a*a,b>>=1;
	}
	return res;
}
int main(){
	int m,k;read(n,m,k);
	for(int i=0;i<n;++i)I.a[i][i]=1;
	for(int i=0;i<n;++i)read(orig.a[i][0]);
	for(int i=1;i<=m;++i)read(X[i],Y[i]);
	ll inv=ksm(m);
	for(int i=0;i<n;++i)M.a[i][i]=1;
	for(int i=1;i<=m;++i){
		int x=X[i]-1,y=Y[i]-1;
		add(M.a[x][x],1LL*inv*(mod-inv2)%mod),add(M.a[x][y],1LL*inv*inv2%mod);
		add(M.a[y][y],1LL*inv*(mod-inv2)%mod),add(M.a[y][x],1LL*inv*inv2%mod);
	}
	mat o=ksm(M,k)*orig;
	for(int i=0;i<n;++i)printf("%d\n",o.a[i][0]);
	return 0;
}