#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6;
const int mod = 1e9 + 7;
int S[N + 1];
int n, x, t;
int cnt[N + 1];
int Pow(int a, int b)
{
int res(1);
while (b)
{
if (b & 1)
res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i(2); i <= N; i++)
if (!S[i])
{
S[i] = i;
for (int j(i * i); j <= N; j += i)
if (!S[j])
S[j] = i;
}
cin >> n;
while (n--)
{
cin >> t;
while (t > 1)
{
cnt[S[t]]++;
t /= S[t];
}
}
cin >> x;
int res(1);
for (int i(1); i <= N; i++)
if (cnt[i])
{
int t = cnt[i];
res = ((res * (Pow(i, t * x + 1) - 1)) % mod * Pow(i - 1, mod - 2) % mod) % mod;
}
cout << res;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwpjb25zdCBpbnQgTiA9IDFlNjsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmludCBTW04gKyAxXTsKaW50IG4sIHgsIHQ7CmludCBjbnRbTiArIDFdOwoKaW50IFBvdyhpbnQgYSwgaW50IGIpCnsKICAgIGludCByZXMoMSk7CiAgICB3aGlsZSAoYikKICAgIHsKICAgICAgICBpZiAoYiAmIDEpCiAgICAgICAgICAgIHJlcyA9IChyZXMgKiBhKSAlIG1vZDsKICAgICAgICBhID0gKGEgKiBhKSAlIG1vZDsKICAgICAgICBiID4+PSAxOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoKc2lnbmVkIG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKCiAgICBmb3IgKGludCBpKDIpOyBpIDw9IE47IGkrKykKICAgICAgICBpZiAoIVNbaV0pCiAgICAgICAgewogICAgICAgICAgICBTW2ldID0gaTsKICAgICAgICAgICAgZm9yIChpbnQgaihpICogaSk7IGogPD0gTjsgaiArPSBpKQogICAgICAgICAgICAgICAgaWYgKCFTW2pdKQogICAgICAgICAgICAgICAgICAgIFNbal0gPSBpOwogICAgICAgIH0KCiAgICBjaW4gPj4gbjsKICAgIHdoaWxlIChuLS0pCiAgICB7CiAgICAgICAgY2luID4+IHQ7CiAgICAgICAgd2hpbGUgKHQgPiAxKQogICAgICAgIHsKICAgICAgICAgICAgY250W1NbdF1dKys7CiAgICAgICAgICAgIHQgLz0gU1t0XTsKICAgICAgICB9CiAgICB9CiAgICAKICAgIGNpbiA+PiB4OwogICAgaW50IHJlcygxKTsKICAgIGZvciAoaW50IGkoMSk7IGkgPD0gTjsgaSsrKQogICAgICAgIGlmIChjbnRbaV0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgdCA9IGNudFtpXTsKICAgICAgICAgICAgcmVzID0gKChyZXMgKiAoUG93KGksIHQgKiB4ICsgMSkgLSAxKSkgJSBtb2QgKiBQb3coaSAtIDEsIG1vZCAtIDIpICUgbW9kKSAlIG1vZDsKICAgICAgICB9CiAgICAKICAgIGNvdXQgPDwgcmVzOwoKICAgIHJldHVybiAwOwp9