// #define _GLIBCXX_DEBUG // for STL debug (optional) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long int; using int64 = long long int; template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; // ModInt begin using ll = long long; template struct ModInt { ll v; ll mod_pow(ll x, ll n) const { return (!n) ? 1 : (mod_pow((x*x)%mod,n/2) * ((n&1)?x:1)) % mod; } ModInt(ll a = 0) : v((a %= mod) < 0 ? a + mod : a) {} ModInt operator+ ( const ModInt& b ) const { return (v + b.v >= mod ? ModInt(v + b.v - mod) : ModInt(v + b.v)); } ModInt operator- () const { return ModInt(-v); } ModInt operator- ( const ModInt& b ) const { return (v - b.v < 0 ? ModInt(v - b.v + mod) : ModInt(v - b.v)); } ModInt operator* ( const ModInt& b ) const {return (v * b.v) % mod;} ModInt operator/ ( const ModInt& b ) const {return (v * mod_pow(b.v, mod-2)) % mod;} bool operator== ( const ModInt &b ) const {return v == b.v;} bool operator!= ( const ModInt &b ) const {return !(*this == b); } ModInt& operator+= ( const ModInt &b ) { v += b.v; if(v >= mod) v -= mod; return *this; } ModInt& operator-= ( const ModInt &b ) { v -= b.v; if(v < 0) v += mod; return *this; } ModInt& operator*= ( const ModInt &b ) { (v *= b.v) %= mod; return *this; } ModInt& operator/= ( const ModInt &b ) { (v *= mod_pow(b.v, mod-2)) %= mod; return *this; } ModInt pow(ll x) { return ModInt(mod_pow(v, x)); } // operator int() const { return int(v); } // operator long long int() const { return v; } }; template ModInt pow(ModInt n, ll k) { return ModInt(n.mod_pow(n.v, k)); } template ostream& operator<< (ostream& out, ModInt a) {return out << a.v;} template istream& operator>> (istream& in, ModInt& a) { in >> a.v; return in; } // ModInt end // 行列ライブラリ // 演算子: 複合代入 (+=, -=), 単項 (-), 二項 (+, -, *, ==) // eigen(N): N*N 単位行列を返す // pow(mat, k): mat の k 乗を返す template struct FixedMatrix { using array_type = array; array_type mat; FixedMatrix(T val = T(0)) { mat.fill(val); } const T& at(int i, int j) const { return mat[i*w + j]; } T& at(int i, int j) { return mat[i*w + j]; } FixedMatrix &operator+=(const FixedMatrix& rhs) { for(size_t i=0; iat(i, j) += rhs.at(i, j); } } return *this; } FixedMatrix operator-() const { FixedMatrix res(*this); for(size_t i=0; i &operator-=(const FixedMatrix& rhs) { return (FixedMatrix(*this) += -rhs); } template FixedMatrix operator*(const FixedMatrix& rhs) { size_t H = h, W = wr, C = w; FixedMatrix res; for(size_t i=0; iat(i, k) * rhs.at(k, j); } } } return res; } FixedMatrix operator+(const FixedMatrix& rhs) { return (FixedMatrix(*this) += rhs); } FixedMatrix operator-(const FixedMatrix &rhs) { return (FixedMatrix(*this) -= rhs); } bool operator==(const FixedMatrix &rhs) const { return this->mat == rhs.mat; } bool operator!=(const FixedMatrix &rhs) const { return !(*this == rhs); } }; template FixedMatrix eigen() { FixedMatrix res(0); for(size_t i=0; i FixedMatrix pow(FixedMatrix mat, long long int k) { FixedMatrix res = eigen(); for(; k>0; k>>=1) { if(k & 1) res = res * mat; mat = mat * mat; } return res; } template ostream& operator<< (ostream& out, FixedMatrix mat) { int H = mat.h, W = mat.w; out << "[" << endl; for(int i=0; i; int main() { ll N, M, K, P, Q; cin >> N >> M >> K >> P >> Q; vector B(N); for(int i=0; i> B[i]; mint X = mint(P) / mint(Q); FixedMatrix mat; mat.at(0, 0) = mat.at(1, 1) = mint(1) - X; mat.at(0, 1) = mat.at(1, 0) = X; mat = pow(mat, K); mint ans(0); // p1 = X * p2 + (1 - X) * p1 // p2 = X * p1 + (1 - X) * p2 for(int i=0; i