#define _USE_MATH_DEFINES #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; template class Operators { public: template const T1 operator+(const T2& right) const{ T1 ans = static_cast( *this ); return ans += right; } template const T1 operator-(const T2& right) const{ T1 ans = static_cast( *this ); return ans -= right; } template const T1 operator*(const T2& right) const{ T1 ans = static_cast( *this ); return ans *= right; } template const T1 operator/(const T2& right) const{ T1 ans = static_cast( *this ); return ans /= right; } template const T1 operator%(const T2& right) const{ T1 ans = static_cast( *this ); return ans %= right; } bool operator!=(const T1& right) const{ const T1& left = static_cast( *this ); return !(left == right); } bool operator>(const T1& right) const{ const T1& left = static_cast( *this ); return right < left; } bool operator<=(const T1& right) const{ const T1& left = static_cast( *this ); return !(right < left); } bool operator>=(const T1& right) const{ const T1& left = static_cast( *this ); return !(left < right); } }; class Mod : public Operators { private: static const int MOD = 1000000007; long long a; public: Mod(){ a = 0; } Mod(long long x){ a = (x % MOD + MOD) % MOD; } Mod& operator+=(const Mod& x){ a = (a + x.a) % MOD; return *this; } Mod& operator-=(const Mod& x){ a = (a - x.a + MOD) % MOD; return *this; } Mod& operator*=(const Mod& x){ a = (a * x.a) % MOD; return *this; } Mod& operator/=(const Mod& x){ // フェルマーの小定理、MODが素数である場合のみ有効 int b = MOD - 2; long long c = x.a; while(b > 0){ if(b & 1){ a *= c; a %= MOD; } c *= c; c %= MOD; b >>= 1; } return *this; } bool operator==(const Mod& x) const{ return a == x.a; } long long getValue(){ return a; } }; // 行列の積 template vector > matrixProduct(const vector >& x, const vector >& y) { int a = x.size(); int b = x[0].size(); int c = y[0].size(); vector > z(a, vector(c, 0)); for(int i=0; i vector > matrixPower(const vector >& x, long long k) { int n = x.size(); vector > y(n, vector(n, 0)); for(int i=0; i > z = x; while(k > 0){ if(k & 1) y = matrixProduct(y, z); z = matrixProduct(z, z); k >>= 1; } return y; } int main() { int n, m, p, q; long long k; cin >> n >> m >> k >> p >> q; vector b(n); for(int i=0; i> b[i]; Mod x = Mod(p) / q; vector > v = { {Mod(1) - x, x}, {x, Mod(1) - x}, }; v = matrixPower(v, k); Mod ans = 0; for(int i=0; i