#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;

template<class T = double>
struct __Complex {
    T x, y;
    __Complex() = default;
    __Complex(const T& x, const T& y) : x(x), y(y) {}
    __Complex& operator+=(const __Complex& b) {
        x += b.x;
        y += b.y;
        return *this;
    }
    __Complex& operator-=(const __Complex& b) {
        x -= b.x;
        y -= b.y;
        return *this;
    }
    __Complex& operator*=(const __Complex& b) {
        __Complex temp = *this;
        temp.x = x * b.x - y * b.y;
        temp.y = x * b.y + y * b.x;
        *this = temp;
        return *this;
    }
    __Complex& operator*=(const double& b) {
        this -> x *= b;
        this -> y *=b;
        return *this;
    }
    __Complex operator+(const __Complex& b) {
        __Complex a = *this;
        a += b;
        return a;
    }
    __Complex operator-(const __Complex& b) {
        __Complex a = *this;
        a -= b;
        return a;
    }
    __Complex operator*(const __Complex& b) {
        __Complex a = *this;
        a *= b;
        return a;
    }
    __Complex conj() {
    	return __Complex(x, -y);
    }
    friend ostream& operator<<(ostream& os, const __Complex& a) {
        os << a.x << " " << a.y;
        return os;
    }
};
using Complex = __Complex<>;
const long double PI = acos(-1.0);
const long double PI2 = PI / 2;
const int CONQUER_BIT = 16;
const int CONQUER_MASK = (1 << CONQUER_BIT) - 1;
const Complex I(0, 1);
vector<Complex> r;
int preLg;
void pre(const int lg) {
    r.resize(1 << lg);
    for (int i = preLg ; i < lg ; i++) {
    	int L = 1 << i;
    	r[L] = Complex(cos(PI2 / L), sin(PI2 / L));
    	for (int j = L + 1 ; j < (L << 1) ; j++) {
    		r[j] = r[j - L] * r[L];
    	}
    }
}
template<class T> long long Tint2(const T val, const int mod) {
	long long v = val;
	return ((v < 0) ? (mod + (v - 1) / 2 % mod) : (v + 1) / 2) % mod;
}
template<class T> struct Poly {
    vector<T> a;
    Poly(const int size) {
        a.resize(size);
    }
    T &operator[](const int x) {
        return a[x];
    }
    void resize(const int n) {
        a.resize(n);
    }
    int size() {
        return a.size();
    }
    void FFT() {
 		int n = a.size();
 		for (int i = n ; i >= 2 ; i >>= 1) {
 			int L = i >> 1;
 			for (int j = 0 ; j != L ; j++) {
 				Complex x = a[j], y = a[j + L];
 				a[j] = x + y;
 				a[j + L] = x - y;
 			}
 			for (int j = i, m = 1 ; j != n ; j += i, m++) {
 				Complex rt = r[m];
 				for (int k = 0 ; k != L ; k++) {
 					Complex x = a[j + k], y = a[j + k + L] * rt;
 					a[j + k] = x + y;
 					a[j + k + L] = x - y;
 				}
 			}
 		}
    }
    void IFFT() {
    	int n = a.size();
    	for (int i = 2 ; i <= n ; i <<= 1) {
    		int L = i >> 1;
    		for (int j = 0 ; j != L ; j++) {
    			Complex x = a[j], y = a[j + L];
 				a[j] = x + y;
 				a[j + L] = x - y;
    		}
    		for (int j = i, m = 1 ; j != n ; j += i, m++) {
 				Complex rt = r[m];
 				for (int k = 0 ; k != L ; k++) {
 					Complex x = a[j + k], y = a[j + k + L];
 					a[j + k] = x + y;
 					a[j + k + L] = (x - y) * rt;
 				}
 			}
    	}
    	double inv = 1.0 / n;
    	for (int i = 0 ; i < n ; i++) {
    		a[i] *= inv;
    	}
    	reverse(begin(a) + 1, end(a));
    }
    void mul(Poly &x, const int mod) {
    	int n = 1, u = a.size(), m = x.size(), lg = 0, len = u + m - 1;
        while (n < len) {
            n <<= 1;
            lg++;
        }
        if (lg > preLg) {
            pre(lg);
            preLg = lg;
        }
        Poly<Complex> P(n), Q(n);
        for (int i = 0 ; i < u ; i++) {
        	P[i] = Complex(a[i] & CONQUER_MASK, a[i] >> CONQUER_BIT);
        }
    	P.FFT();
        Poly<Complex> _Q(P);
        for (int i = 0 ; i < m ; i++) {
    		Q[i] = Complex(x[i] & CONQUER_MASK, x[i] >> CONQUER_BIT);
        }
        Q.FFT();
        P[0] *= Q[0].x * 2;
        _Q[0] *= Q[0].y * 2;
        for (int d = 0 ; d < lg ; d++) {
        	int L = 1 << d, msk = L - 1;
        	for (int i = L ; i < (L << 1) ; i++) {
        		Complex &p = Q[i], q = Q[i ^ msk].conj();
        		Complex a = (p + q), b = (q - p) * I;
        		P[i] *= a;
        		_Q[i] *= b;
        	}
        }
    	P.IFFT();
    	_Q.IFFT();
    	resize(len);
    	for (int i = 0 ; i < len ; i++) {
    		long long cur = (Tint2(_Q[i].y, mod) << (CONQUER_BIT << 1))
    		 	+ (Tint2(_Q[i].x + P[i].y, mod) << CONQUER_BIT)
    		 	+ (Tint2(P[i].x, mod));
    		 a[i] = cur % mod;
    	}
    }
}; // Poly


const int mod = 1e9 + 9; 
int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b; 
}
int dec(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b; 
}
int mul(int a, int b) {
    return 1ll * a * b % mod;
}
void Add(int &a, int b) {
    a = add(a, b);
}
void Dec(int &a, int b) {
    a = dec(a, b);
}
void Mul(int &a, int b) {
    a = mul(a, b);
}
int ksm(int a, int b) {
    int c = 1; 
    for(; b; b >>= 1, Mul(a, a))
    if(b & 1) Mul(c, a);
    return c; 
}

namespace poly {
	using u64 = unsigned long long;
    std :: vector <int> conv(std :: vector <int> P, std :: vector <int> Q) {
        if(P.size() == 0 || Q.size() == 0) return {};
        Poly<int> p(P.size());
        for(int i = 0; i < P.size(); i++)
            p[i] = P[i];
        Poly<int> q(Q.size());
        for(int i = 0; i < Q.size(); i++)
            q[i] = Q[i];
        p.mul(q, mod);
        P.clear();
        for(int i = 0; i < p.size(); i++)
            P.pb(p[i]);
        return P; 
    }
    std :: vector <int> inv(std :: vector <int> a, int n) {
        int l = 1; 
        for(; l < n; l <<= 1);
        std :: vector <int> b(l), c, d;
        a.resize(l);
        b[0] = ksm(a[0], mod - 2);
        for(int r = 2; r <= l; r <<= 1){
            c.resize(r);
            d.resize(r);
            for(int i = 0; i < r; i++) c[i] = a[i];
            for(int i = 0; i < (r >> 1); i++) d[i] = b[i];
            c = conv(c, d);
            for(int i = 1; i < (r >> 1); i++) c[i]=0;
            c[0] = mod - 1;
            d = conv(c, d);
            for(int i = r >> 1; i < r; i++) b[i] = (mod - d[i]) % mod;
        }
        b.resize(n);
        return b;
    }

    vector <int> integ(vector <int> f){
        f.push_back(0);
        for(int i = (int)f.size()-2; ~i; i--) f[i + 1] = mul(ksm(i + 1, mod - 2), f[i]);
        f[0] = 0; return f;
    }
    vector <int> deriv(vector <int> f){
        for(int i = 1; i < (int)f.size(); i++) f[i-1] = mul(f[i], i); f.pop_back(); 
        return f;
    }
    vector <int> ln(vector <int> f, int deg){ 
        vector <int> g = integ(conv(deriv(f), inv(f, deg))); 
        g.resize(deg); return g; 
    }
    vector <int> exp(vector <int> a, int deg){
        vector <int> b(1, 1), c; a.resize(deg << 1);
        for(int lim = 2; lim < (deg << 1); lim <<= 1){
            c = ln(b, lim);
            for(int i = 0; i < lim; i++) assert(i < c.size()) , c[i] = dec(a[i], c[i]);
            Add(c[0], 1); b = conv(b, c); b.resize(lim);
        } b.resize(deg); return b;
    }
    
	int eval(std::vector<int> P, std::vector<int> Q, int m) {
		if(m == 0) {
			return P[0];
		}
		std::vector<int> negQ = Q;
		for(int i = 1;i < (int) negQ.size();i += 2) {
			negQ[i] = (mod - negQ[i]) % mod;
		}
		P = conv(P, negQ);
		Q = conv(Q, negQ);
		std::vector<int> remP, remQ;
		for(int i = 0;i < (int) Q.size();i += 2) remQ.push_back(Q[i]);
		for(int i = m % 2;i < (int) P.size();i += 2) remP.push_back(P[i]);
		return eval(remP, remQ, m / 2);
	}
}
cs int N = 1e5 + 5; 

int n, m;

const int p = mod; 
vector<int> berlekamp_massey(const vector<int> &a) {
    vector<int> v, last; // v is the answer, 0-based
    int k = -1, delta = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        int tmp = 0;
        for (int j = 0; j < (int)v.size(); j++)
            tmp = (tmp + (long long)a[i - j - 1] * v[j]) % p;
        if (a[i] == tmp) continue;
        if (k < 0) {
            k = i; delta = (a[i] - tmp + p) % p;
            v = vector<int>(i + 1); continue; 
        }
        vector<int> u = v;
        int val = (long long)(a[i] - tmp + p) * ksm(delta, p - 2) % p;
        if (v.size() < last.size() + i - k)
            v.resize(last.size() + i - k);
        (v[i - k - 1] += val) %= p;
        for (int j = 0; j < (int)last.size(); j++) {
            v[i - k + j] = (v[i - k + j] - (long long)val * last[j]) % p;
        if (v[i - k + j] < 0) v[i - k + j] += p; }
        if ((int)u.size() - i < (int)last.size() - k) {
            last = u; k = i; delta = a[i] - tmp;
            if (delta < 0) delta += p; 
        } 
    }
    for (auto &x : v) x = (p - x) % p;
    v.insert(v.begin(), 1); //一般是需要最小递推式的, 处理一下
    return v; 
}

int main() { 
    #ifdef zqj 
    freopen("1.in","r",stdin);
    #endif

    cin >> n >> m; 
    int d = n * n; 

    
    vector <int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    vector <int> fc(d + 1), ifc(d + 1);
    fc[0] = ifc[0] = 1; 
    for(int i = 1; i <= d; i++)
        fc[i] = mul(fc[i - 1], i);
    ifc[d] = ksm(fc[d], mod - 2);
    for(int i = d - 1; i; i--)
        ifc[i] = mul(ifc[i + 1], i + 1);

    // vector<int> check = poly :: ln({1, mod - 1}, 5);
    // vector<int> iv = poly :: inv({1, mod - 1}, 10);
    // for(int x : check) cout << x<< ' '; cout <<endl;
    // check = poly :: exp(check, 5);
    // for(int x : check) cout << x<< ' '; cout <<endl;
    // for(int x : iv) cout << x<< ' '; cout <<endl;

    vector <int> aa(n + 1), bb(n + 1);
    aa[0] = bb[0] = 1; 
    for(int i = 1; i <= n; i++) aa[i] = mod - a[i], bb[i] = mod - b[i];
    vector <int> ff = poly :: inv(aa, d + 1);
    vector <int> gg = poly :: inv(bb, d + 1);
    
    for(int i = 0; i <= d; i++)
        Mul(ff[i], ifc[i]), Mul(gg[i], ifc[i]);
    ff = poly :: conv(ff, gg);
    for(int i = 0; i <= d; i++)
        Mul(ff[i], fc[i]);
    ff.resize(d + 1); 

    aa = poly :: ln(aa, d + 1);
    bb = poly :: ln(bb, d + 1);
    aa[0] = bb[0] = n;  

    for(int i = 1; i <= d; i++)
        Mul(aa[i], mod - ifc[i - 1]);
    for(int i = 1; i <= d; i++)
        Mul(bb[i], mod - ifc[i - 1]);
    
    vector <int> c = poly :: conv(aa, bb);
    c.resize(d + 1);
    for(int i = 1; i <= d; i++)
        Mul(c[i], mod - fc[i - 1]);
    c[0] = 0; 
    c = poly :: exp(c, d + 1);

    vector <int> up = poly :: conv(ff, c);
    up.resize(d + 1);
    int ans = poly :: eval(up, c, m);
    cout << ans << endl;

}
//     for(int i = 0; i <= d; i++) cout << f[i] << ' '; cout << endl;
//     vector <int> v = berlekamp_massey(f); 
//     cout << "fasfsdasd " << v.size() << endl;
//     for(int x : v)cout << x << ' '; cout << endl;
//     vector <int> vvv = poly :: inv(v, d + 1);
//     for(int x : vvv) cout << x<< ' '; cout << endl;
//     std :: vector <int> fff = poly :: inv(f, n * n + 1);
//     for(int i = 0; i < fff.size(); i++) cout << fff[i] << ' '; cout << endl;
//     cout << ans << '\n'; 
// }