#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) {
        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;
    }
    
	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;
int main() { 
    #ifdef zqj 
    freopen("1.in","r",stdin);
    #endif

    cin >> n >> m; 
    vector <int> a(n + 1), b(n + 1), f(m + 1), g(m + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    f[0] = 1; 
    g[0] = 1; 
    for(int i = 1; i <= m; i++) 
    for(int j = 1; j <= min(i, n); j++)
    Add(f[i], mul(f[i - j], a[j]));
    for(int i = 1; i <= m; i++) 
    for(int j = 1; j <= min(i, n); j++)
    Add(g[i], mul(g[i - j], b[j]));
    
    vector <int> fc(m + 1), ifc(m + 1);
    fc[0] = ifc[0] = 1; 
    for(int i = 1; i <= m; i++)
        fc[i] = mul(fc[i - 1], i);
    ifc[m] = ksm(fc[m], mod - 2);
    for(int i = m - 1; i; i--)
        ifc[i] = mul(ifc[i + 1], i + 1);
    
    vector <int> ans(m + 1);
    for(int i = 0; i <= m; i++)
    for(int j = 0; j <= i; j++)
        Add(ans[i], mul(mul(ifc[j], ifc[i - j]), mul(f[j], g[i - j])));
    // for(int i = 0; i <= m; i++)
    //     cout << mul(ans[i], fc[i]) << ' '; cout << endl;
    cout << mul(ans[m], fc[m]) << ' ';
}