/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;

template<class T> bool ckmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template <class X, class Y>
std::ostream & operator << (std::ostream & os, std::pair <X, Y> const& p) {
    return os << p.first << " " << p.second;
}

template <class Ch, class Tr, class Container>
std::basic_ostream <Ch, Tr> & operator << (std::basic_ostream <Ch, Tr>& os, Container const& x) {
    bool first = true;
    for(auto& y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}


#include <iostream>
#include <assert.h>



#include <string>
#include <stdexcept>

#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
		if(!(condition)) { \
			throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
		}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif





template <typename T, typename = std::true_type>
struct IdentityHelper;

template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
    static T identity() {
        return 1;
    }
};

template <typename T>
T identity() {
    return IdentityHelper<T>::identity();
}



/**
* ax + by = result
*/
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    T d = extendedGcd(b % a, a, y, x);
    x -= (b / a) * y;
    return d;
}

template <typename T>
class Zn {
public:
    Zn(): value(0) {
    }

    Zn(int64_t value): value(value) {
        int x = static_cast<int>(value % mod());
        if (x < 0) {
            x += mod();
        }
        this->value = x;
    }

    template <typename U>
    static Zn valueOf(U value) {
        int x = static_cast<int>(value % mod());
        if (x < 0) {
            x += mod();
        }
        return Zn(x);
    }

    static Zn rawValueOf(int value) {
        SPCPPL_ASSERT(value >= 0 && value < mod());
        return Zn(value);
    }

    template <typename U>
    Zn& operator=(U rhs) {
        return *this = Zn::valueOf(rhs);
    }


    Zn& operator+=(const Zn& rhs) {
        value += rhs.value;
        if (value >= mod()) {
            value -= mod();
        }
        return *this;
    }

    template <typename U>
    Zn& operator+=(U rhs) {
        return *this += Zn::valueOf(rhs);
    }

    Zn& operator-=(const Zn& rhs) {
        value -= rhs.value;
        if (value < 0) {
            value += mod();
        }
        return *this;
    }

    template <typename U>
    Zn& operator-=(U rhs) {
        return *this -= Zn::valueOf(rhs);
    }

    Zn& operator*=(const Zn& rhs) {
        long long result = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        value = static_cast<int>(result % mod());
        return *this;
    }

    template <typename U>
    Zn& operator*=(U rhs) {
        return *this *= Zn::valueOf(rhs);
    }

    Zn operator-() const {
        if (value == 0) {
            return *this;
        }
        else {
            return Zn(mod() - value);
        }
    }

    Zn& operator/=(const Zn& rhs) {
        return *this *= rhs.inversed();
    }

    template <typename U>
    Zn& operator/=(U rhs) {
        return *this /= Zn::valueOf(rhs);
    }

    Zn inv() const {
        return inversed();
    }

    inline Zn inversed() const {
        SPCPPL_ASSERT(value != 0);

        int x, y;
        int gcd = extendedGcd(value, mod(), x, y);
        (void) gcd;
        SPCPPL_ASSERT(gcd == 1);

        if (x < 0) {
            x += mod();
        }
        return Zn(x);
    }

    template <typename U>
    friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);

    template <typename U>
    friend std::istream& operator>>(std::istream&, Zn<U>& zn);

    template <typename U>
    friend bool operator==(const Zn<U>& lhs, const Zn<U>& rhs);

    int intValue() const {
        return value;
    }

    operator int64_t() const {
        return value;
    }

    constexpr static int mod() {
        return T::value;
    }

private:
    int value;

    template <int N = T::value>
    static constexpr bool correct_or_runtime(int) {
        return N > 0 && N <= (1 << 30);
    }
    static constexpr bool correct_or_runtime(...) {
        return true;
    }
    static_assert(
            std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
            "T::value must be int"
    );
    static_assert(correct_or_runtime(0), "Mod has to be positive integer up to 1 << 30");
};

template <typename T>
bool operator==(const Zn<T>& lhs, const Zn<T>& rhs) {
    return lhs.value == rhs.value;
}

template <typename T, typename U>
bool operator==(const Zn<T>& lhs, U rhs) {
    return lhs == Zn<T>::valueOf(rhs);
}

template <typename T, typename U>
bool operator==(U lhs, const Zn<T>& rhs) {
    return rhs == lhs;
}

template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
    return !(lhs == rhs);
}

template <typename T, typename U>
bool operator!=(const Zn<T>& lhs, U rhs) {
    return !(lhs == rhs);
}

template <typename T, typename U>
bool operator!=(U lhs, const Zn<T>& rhs) {
    return !(lhs == rhs);
}

template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
    Zn<T> copy = lhs;
    return copy += rhs;
}

template <typename T, typename U>
Zn<T> operator+(const Zn<T>& lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy += rhs;
}

template <typename T, typename U>
Zn<T> operator+(U lhs, const Zn<T>& rhs) {
    return rhs + lhs;
}

template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
    Zn<T> copy = lhs;
    return copy -= rhs;
}

template <typename T, typename U>
Zn<T> operator-(const Zn<T>& lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy -= rhs;
}

template <typename T, typename U>
Zn<T> operator-(U lhs, const Zn<T>& rhs) {
    return Zn<T>::valueOf(lhs) - rhs;
}

template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
    Zn<T> copy = lhs;
    return copy *= rhs;
}

template <typename T, typename U>
Zn<T> operator*(const Zn<T>& lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy *= rhs;
}

template <typename T, typename U>
Zn<T> operator*(U lhs, const Zn<T>& rhs) {
    return rhs * lhs;
}

template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
    Zn<T> copy = lhs;
    return copy /= rhs;
}

template <typename T, typename U>
Zn<T> operator/(const Zn<T>& lhs, U rhs) {
    Zn<T> copy = lhs;
    return copy /= rhs;
}

template <typename T, typename U>
Zn<T> operator/(U lhs, const Zn<T>& rhs) {
    return Zn<T>::valueOf(lhs) / rhs;
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
    return stream << zn.value;
}

template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
    int64_t value;
    stream >> value;
    zn.value = static_cast<int>(value % T::value);
    return stream;
}

template <typename T>
struct IdentityHelper<Zn<T>> {
    static Zn<T> identity() {
        return Zn<T>::valueOf(1);
    }
};

template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;

using Zn7 = ZnConst<1000000007>;






#include <cstdlib>

#ifndef SPCPPL_IGNORE_ASSERTS

void assert_re(bool value) {
    if (!value) {
        std::exit(1);
    }
}

void assert_tl(bool value) {
    if (!value) {
        while (true) {
        }
    }
}

void assert_wa(bool value) {
    if (!value) {
        std::cout << "karamba";
        std::exit(0);
    }
}

#else
#define assert_re(x)
	#define assert_tl(x)
	#define assert_wa(x)
#endif



using namespace std;
namespace algebra {
    const int inf = 1e9;
    const int magic = 500; // threshold for sizes to run the naive algo

    namespace fft {
        const int maxn = 1 << 17;

        typedef double ftype;
        typedef complex<ftype> point;

        vector<point> w(maxn);
        vector<point> A(maxn), B(maxn);
        vector<point> C(maxn), D(maxn);
        const ftype pi = acos(-1);
        bool initiated = 0;

        void init(int n) {
            if (!initiated or n > w.size()) {
                w.resize(n);
                A.resize(n);
                B.resize(n);
                C.resize(n);
                D.resize(n);
                for (int i = 1; i < w.size(); i *= 2) {
                    for (int j = 0; j < i; j++) {
                        w[i + j] = polar(ftype(1), pi * j / i);
                    }
                }
                initiated = 1;
            }
        }

        template<typename T>
        void fft(T *in, point *out, int n, int k = 1) {
            if (n == 1) {
                *out = *in;
            } else {
                n /= 2;
                fft(in, out, n, 2 * k);
                fft(in + k, out + n, n, 2 * k);
                for (int i = 0; i < n; i++) {
                    auto t = out[i + n] * w[i + n];
                    out[i + n] = out[i] - t;
                    out[i] += t;
                }
            }
        }

        template<typename T>
        void mul_slow(vector<T> &a, const vector<T> &b) {
            if (not a.empty() or not b.empty()) {
                vector<T> res(a.size() + b.size() - 1);
                for (size_t i = 0; i < a.size(); i++) {
                    for (size_t j = 0; j < b.size(); j++) {
                        res[i + j] = res[i + j] + a[i] * b[j];
                    }
                }
                a = res;
            }
        }


        template<typename T>
        void mul(vector<T> &a, const vector<T> &b) {
            if (min(a.size(), b.size()) < magic) {
                mul_slow(a, b);
                return;
            }
            static const int shift = 15, mask = (1 << shift) - 1;
            size_t n = a.size() + b.size() - 1;
            while (__builtin_popcount(n) != 1) {
                n++;
            }
            a.resize(n);
            init(n);
            for (size_t i = 0; i < n; i++) {
                A[i] = point(a[i] & mask, a[i] >> shift);
                if (i < b.size()) {
                    B[i] = point(b[i] & mask, b[i] >> shift);
                } else {
                    B[i] = 0;
                }
            }
            fft(A.data(), C.data(), n);
            fft(B.data(), D.data(), n);
            for (size_t i = 0; i < n; i++) {
                point c0 = C[i] + conj(C[(n - i) % n]);
                point c1 = C[i] - conj(C[(n - i) % n]);
                point d0 = D[i] + conj(D[(n - i) % n]);
                point d1 = D[i] - conj(D[(n - i) % n]);
                A[i] = c0 * d0 - point(0, 1) * c1 * d1;
                B[i] = c0 * d1 + d0 * c1;
            }
            fft(A.data(), C.data(), n);
            fft(B.data(), D.data(), n);
            reverse(C.begin() + 1, C.begin() + n);
            reverse(D.begin() + 1, D.begin() + n);
            int t = 4 * n;
            for (size_t i = 0; i < n; i++) {
                int64_t A0 = llround(real(C[i]) / t);
                T A1 = llround(imag(D[i]) / t);
                T A2 = llround(imag(C[i]) / t);
                a[i] = A0 + (A1 << shift) + (A2 << 2 * shift);
            }
            return;
        }
    }
    template<typename T>
    T bpow(T x, size_t n) {
        return n ? n % 2 ? x * bpow(x, n - 1) : bpow(x * x, n / 2) : T(1);
    }
    template<typename T>
    T bpow(T x, size_t n, T m) {
        return n ? n % 2 ? x * bpow(x, n - 1, m) % m : bpow(x * x % m, n / 2, m) : T(1);
    }
    template<typename T>
    T gcd(const T &a, const T &b) {
        return b == T(0) ? a : gcd(b, a % b);
    }
    template<typename T>
    T nCr(T n, int r) { // runs in O(r)
        T res(1);
        for(int i = 0; i < r; i++) {
            res *= (n - T(i));
            res /= (i + 1);
        }
        return res;
    }

    template<typename T>
    struct poly {
        vector<T> a;

        void normalize() { // get rid of leading zeroes
            while(!a.empty() && a.back() == T(0)) {
                a.pop_back();
            }
        }

        poly(){}
        poly(T a0) : a{a0}{normalize();}
        poly(vector<T> t) : a(t){normalize();}

        poly operator += (const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for(size_t i = 0; i < t.a.size(); i++) {
                a[i] += t.a[i];
            }
            normalize();
            return *this;
        }
        poly operator -= (const poly &t) {
            a.resize(max(a.size(), t.a.size()));
            for(size_t i = 0; i < t.a.size(); i++) {
                a[i] -= t.a[i];
            }
            normalize();
            return *this;
        }
        poly operator + (const poly &t) const {return poly(*this) += t;}
        poly operator - (const poly &t) const {return poly(*this) -= t;}

        poly mod_xk(size_t k) const { // get same polynomial mod x^k
            k = min(k, a.size());
            return vector<T>(begin(a), begin(a) + k);
        }
        poly mul_xk(size_t k) const { // multiply by x^k
            poly res(*this);
            res.a.insert(begin(res.a), k, 0);
            return res;
        }
        poly div_xk(size_t k) const { // divide by x^k, dropping coefficients
            k = min(k, a.size());
            return vector<T>(begin(a) + k, end(a));
        }
        poly substr(size_t l, size_t r) const { // return mod_xk(r).div_xk(l)
            l = min(l, a.size());
            r = min(r, a.size());
            return vector<T>(begin(a) + l, begin(a) + r);
        }
        poly inv(size_t n) const { // get inverse series mod x^n
            assert(!is_zero());
            poly ans = a[0].inv();
            size_t a = 1;
            while(a < n) {
                poly C = (ans * mod_xk(2 * a)).substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);
        }

        poly operator *= (const poly &t) {fft::mul(a, t.a); normalize(); return *this;}
        poly operator * (const poly &t) const {return poly(*this) *= t;}

        poly reverse(size_t n, bool rev = 0) const { // reverses and leaves only n terms
            poly res(*this);
            if(rev) { // If rev = 1 then tail goes to head
                res.a.resize(max(n, res.a.size()));
            }
            std::reverse(res.a.begin(), res.a.end());
            return res.mod_xk(n);
        }

        pair<poly, poly> divmod_slow(const poly &b) const { // when divisor or quotient is small
            vector<T> A(a);
            vector<T> res;
            while(A.size() >= b.a.size()) {
                res.push_back(A.back() / b.a.back());
                if(res.back() != T(0)) {
                    for(size_t i = 0; i < b.a.size(); i++) {
                        A[A.size() - i - 1] -= res.back() * b.a[b.a.size() - i - 1];
                    }
                }
                A.pop_back();
            }
            std::reverse(begin(res), end(res));
            return {res, A};
        }

        pair<poly, poly> divmod(const poly &b) const { // returns quotiend and remainder of a mod b
            if(deg() < b.deg()) {
                return {poly{0}, *this};
            }
            int d = deg() - b.deg();
            if(min(d, b.deg()) < magic) {
                return divmod_slow(b);
            }
            poly D = (reverse(d + 1) * b.reverse(d + 1).inv(d + 1)).mod_xk(d + 1).reverse(d + 1, 1);
            return {D, *this - D * b};
        }

        poly operator / (const poly &t) const {return divmod(t).first;}
        poly operator % (const poly &t) const {return divmod(t).second;}
        poly operator /= (const poly &t) {return *this = divmod(t).first;}
        poly operator %= (const poly &t) {return *this = divmod(t).second;}
        poly operator *= (const T &x) {
            for(auto &it: a) {
                it *= x;
            }
            normalize();
            return *this;
        }
        poly operator /= (const T &x) {
            for(auto &it: a) {
                it /= x;
            }
            normalize();
            return *this;
        }
        poly operator * (const T &x) const {return poly(*this) *= x;}
        poly operator / (const T &x) const {return poly(*this) /= x;}

        T eval(T x) const { // evaluates in single point x
            T res(0);
            for(int i = int(a.size()) - 1; i >= 0; i--) {
                res *= x;
                res += a[i];
            }
            return res;
        }

        T& lead() { // leading coefficient
            return a.back();
        }
        int deg() const { // degree
            return a.empty() ? -inf : a.size() - 1;
        }
        bool is_zero() const { // is polynomial zero
            return a.empty();
        }
        T operator [](int idx) const {
            return idx >= (int)a.size() || idx < 0 ? T(0) : a[idx];
        }

        T& coef(size_t idx) { // mutable reference at coefficient
            return a[idx];
        }
        bool operator == (const poly &t) const {return a == t.a;}
        bool operator != (const poly &t) const {return a != t.a;}

        poly deriv() { // calculate derivative
            vector<T> res;
            for(int i = 1; i <= deg(); i++) {
                res.push_back(T(i) * a[i]);
            }
            return res;
        }
        poly integr() { // calculate integral with C = 0
            vector<T> res = {0};
            for(int i = 0; i <= deg(); i++) {
                res.push_back(a[i] / T(i + 1));
            }
            return res;
        }
        size_t leading_xk() const { // Let p(x) = x^k * t(x), return k
            if(is_zero()) {
                return inf;
            }
            int res = 0;
            while(a[res] == T(0)) {
                res++;
            }
            return res;
        }
        poly log(size_t n) { // calculate log p(x) mod x^n
            assert(a[0] == T(1));
            return (deriv().mod_xk(n) * inv(n)).integr().mod_xk(n);
        }
        poly exp(size_t n) { // calculate exp p(x) mod x^n
            if(is_zero()) {
                return T(1);
            }
            assert(a[0] == T(0));
            poly ans = T(1);
            size_t a = 1;
            while(a < n) {
                poly C = ans.log(2 * a).div_xk(a) - substr(a, 2 * a);
                ans -= (ans * C).mod_xk(a).mul_xk(a);
                a *= 2;
            }
            return ans.mod_xk(n);

        }
        poly pow_slow(size_t k, size_t n) { // if k is small
            return k ? k % 2 ? (*this * pow_slow(k - 1, n)).mod_xk(n) : (*this * *this).mod_xk(n).pow_slow(k / 2, n) : T(1);
        }
        poly pow(size_t k, size_t n) { // calculate p^k(n) mod x^n
            if(is_zero()) {
                return *this;
            }
            if(k < magic) {
                return pow_slow(k, n);
            }
            int i = leading_xk();
            T j = a[i];
            poly t = div_xk(i) / j;
            return bpow(j, k) * (t.log(n) * T(k)).exp(n).mul_xk(i * k).mod_xk(n);
        }
        poly mulx(T x) { // component-wise multiplication with x^k
            T cur = 1;
            poly res(*this);
            for(int i = 0; i <= deg(); i++) {
                res.coef(i) *= cur;
                cur *= x;
            }
            return res;
        }
        poly mulx_sq(T x) { // component-wise multiplication with x^{k^2}
            T cur = x;
            T total = 1;
            T xx = x * x;
            poly res(*this);
            for(int i = 0; i <= deg(); i++) {
                res.coef(i) *= total;
                total *= cur;
                cur *= xx;
            }
            return res;
        }
        vector<T> chirpz_even(T z, int n) { // P(1), P(z^2), P(z^4), ..., P(z^2(n-1))
            int m = deg();
            if(is_zero()) {
                return vector<T>(n);
            }
            vector<T> vv(m + n);
            T zi = z.inv();
            T zz = zi * zi;
            T cur = zi;
            T total = 1;
            for(int i = 0; i <= max(n - 1, m); i++) {
                if(i <= m) {vv[m - i] = total;}
                if(i < n) {vv[m + i] = total;}
                total *= cur;
                cur *= zz;
            }
            poly w = (mulx_sq(z) * vv).substr(m, m + n).mulx_sq(z);
            vector<T> res(n);
            for(int i = 0; i < n; i++) {
                res[i] = w[i];
            }
            return res;
        }
        vector<T> chirpz(T z, int n) { // P(1), P(z), P(z^2), ..., P(z^(n-1))
            auto even = chirpz_even(z, (n + 1) / 2);
            auto odd = mulx(z).chirpz_even(z, n / 2);
            vector<T> ans(n);
            for(int i = 0; i < n / 2; i++) {
                ans[2 * i] = even[i];
                ans[2 * i + 1] = odd[i];
            }
            if(n % 2 == 1) {
                ans[n - 1] = even.back();
            }
            return ans;
        }
        template<typename iter>
        vector<T> eval(vector<poly> &tree, int v, iter l, iter r) { // auxiliary evaluation function
            if(r - l == 1) {
                return {eval(*l)};
            } else {
                auto m = l + (r - l) / 2;
                auto A = (*this % tree[2 * v]).eval(tree, 2 * v, l, m);
                auto B = (*this % tree[2 * v + 1]).eval(tree, 2 * v + 1, m, r);
                A.insert(end(A), begin(B), end(B));
                return A;
            }
        }

        vector<T> eval(vector<T> x) { // evaluate polynomial in (x1, ..., xn)
            int n = x.size();
            if(is_zero()) {
                return vector<T>(n, T(0));
            }
            vector<poly> tree(4 * n);
            build(tree, 1, begin(x), end(x));
            return eval(tree, 1, begin(x), end(x));
        }
        template<typename iter>
        poly inter(vector<poly> &tree, int v, iter l, iter r, iter ly, iter ry) { // auxiliary interpolation function
            if(r - l == 1) {
                return {*ly / a[0]};
            } else {
                auto m = l + (r - l) / 2;
                auto my = ly + (ry - ly) / 2;
                auto A = (*this % tree[2 * v]).inter(tree, 2 * v, l, m, ly, my);
                auto B = (*this % tree[2 * v + 1]).inter(tree, 2 * v + 1, m, r, my, ry);
                return A * tree[2 * v + 1] + B * tree[2 * v];
            }
        }
    };
    template<typename T>
    poly<T> operator * (const T& a, const poly<T>& b) {
        return b * a;
    }

    template<typename T>
    poly<T> xk(int k) { // return x^k
        return poly<T>{1}.mul_xk(k);
    }

    template<typename T>
    T resultant(poly<T> a, poly<T> b) { // computes resultant of a and b
        if(b.is_zero()) {
            return 0;
        } else if(b.deg() == 0) {
            return bpow(b.lead(), a.deg());
        } else {
            int pw = a.deg();
            a %= b;
            pw -= a.deg();
            T mul = bpow(b.lead(), pw) * T((b.deg() & a.deg() & 1) ? -1 : 1);
            T ans = resultant(b, a);
            return ans * mul;
        }
    }
    template<typename iter>
    poly<typename iter::value_type> kmul(iter L, iter R) { // computes (x-a1)(x-a2)...(x-an) without building tree
        if(R - L == 1) {
            return vector<typename iter::value_type>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return kmul(L, M) * kmul(M, R);
        }
    }
    template<typename T, typename iter>
    poly<T> build(vector<poly<T>> &res, int v, iter L, iter R) { // builds evaluation tree for (x-a1)(x-a2)...(x-an)
        if(R - L == 1) {
            return res[v] = vector<T>{-*L, 1};
        } else {
            iter M = L + (R - L) / 2;
            return res[v] = build(res, 2 * v, L, M) * build(res, 2 * v + 1, M, R);
        }
    }

    template<typename T>
    poly<T> build(const vector<T> roots) {
        if (roots.empty()) {
            return 1;
        }
        vector<poly<T>> tree(4 * roots.size());
        return build(tree, 1, begin(roots), end(roots));
    }

    template<typename T>
    poly<T> inter(vector<T> x, vector<T> y) { // interpolates minimum polynomial from (xi, yi) pairs
        int n = x.size();
        vector<poly<T>> tree(4 * n);
        return build(tree, 1, begin(x), end(x)).deriv().inter(tree, 1, begin(x), end(x), begin(y), end(y));
    }

    template<typename T>
    ostream& operator<<(ostream &os, const poly<T> P) {
        for(auto it: P.a) {
            os << it << ' ';
        }
        return os << endl;
    }
};

using namespace algebra;

//const int mod = 1e9 + 7;
//typedef modular<mod> base;
//typedef poly<base> polyn;

//using namespace algebra;

//signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    int n = 100000;
//    polyn a;
//    vector<base> x;
//    for(int i = 0; i <= n; i++) {
//        a.a.push_back(1 + rand() % 100);
//        x.push_back(1 + rand() % (2 * n));
//    }
//    sort(begin(x), end(x));
//    x.erase(unique(begin(x), end(x)), end(x));
//    auto b = a.eval(x);
//    cout << clock() / double(CLOCKS_PER_SEC) << endl;
//    auto c = inter(x, b);
//    polyn md = kmul(begin(x), end(x));
//    cout << clock() / double(CLOCKS_PER_SEC) << endl;
//    assert(c == a % md);
//    return 0;
//}
//
// Created by aryssoncf on 30/10/2019.
//

#include <cassert>


#include <vector>
#include <cstddef>

bool isPrime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2;
}

bool isPrime(int64_t n) {
    for (int64_t i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2;
}

std::vector<bool> primeMap(std::size_t maxN) {
    std::vector<bool> prime(maxN + 1, true);

    prime[0] = false;
    prime[1] = false;

    for (std::size_t i = 2; i * i <= maxN; ++i) {
        if (prime[i]) {
            if (i * 1ULL * i <= maxN) {
                for (std::size_t j = i * i; j <= maxN; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
    return prime;
}

std::vector<int> allPrimes(int maxN) {
    std::vector<int> result;
    result.reserve(maxN);
    std::vector<bool> map = primeMap(maxN);
    for (int i = 0; i <= maxN; i++) {
        if (map[i]) {
            result.push_back(i);
        }
    }
    return result;
}

int nextPrime(int n) {
    while (!isPrime(n)) {
        ++n;
    }
    return n;
}





using namespace std;

template <typename T>
std::vector<T> unsortedDivisors(const T& n) {
    std::vector<T> result;
    for (T i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            result.push_back(i);
            if (i * i != n) {
                result.push_back(n / i);
            }
        }
    }
    return result;
}

template <typename T>
std::vector<T> sortedDivisors(const T& n) {
    return sorted(unsortedDivisors(n));
}

template<typename T>
std::vector<T> primeDivisors(T n) {
    std::vector<T> result;
    for (T i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            result.push_back(i);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        result.push_back(n);
    }
    return result;
}

template<typename T>
vector<pair<T, int>> factorize(T n) {
    vector<pair<T, int>> result;
    for (T i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int power = 0;
            while (n % i == 0) {
                power++;
                n /= i;
            }
            result.push_back({i, power});
        }
    }
    if (n > 1) {
        result.push_back({n, 1});
    }
    return result;
}



#ifndef JHELPER_EXAMPLE_PROJECT_NUMBERTHEORY_HPP
#define JHELPER_EXAMPLE_PROJECT_NUMBERTHEORY_HPP

#endif //JHELPER_EXAMPLE_PROJECT_NUMBERTHEORY_HPP

using namespace std;

int find_generator(long long MOD) {
    vector<long long> divisors = primeDivisors(MOD - 1);
    for (int root = 1; ; root++) {
        bool valid = true;
        for (int d: divisors) {
            if (bpow((long long)root, (MOD - 1) / d, MOD) == 1) {
                valid = false;
                break;
            }
        }
        if (valid) {
            return root;
        }
    }
}





template <typename T>
T binpow(T base, long long power) {
    SPCPPL_ASSERT(power >= 0);
//    T result = identity<T>();
    T result = (T)1;
    while (power > 0) {
        if (power & 1) {
            result *= base;
        }
        power >>= 1;
        base *= base;
    }
    return result;
}



//
// Created by aryssoncf on 25/10/2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_FASTFOURIERTRANSFORM_HPP
#define JHELPER_EXAMPLE_PROJECT_FASTFOURIERTRANSFORM_HPP

#endif //JHELPER_EXAMPLE_PROJECT_FASTFOURIERTRANSFORM_HPP

#include <complex>



//
// Created by aryssoncf on 25/10/2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_FFT_HPP
#define JHELPER_EXAMPLE_PROJECT_FFT_HPP

#endif //JHELPER_EXAMPLE_PROJECT_FFT_HPP






using namespace std;

template<typename T>
class FFT {
protected:
    virtual int result_length(int first_length, int second_length) = 0;
    virtual long long result_length_power(long long first_length, long long second_length) = 0;

    unsigned nextpow2(unsigned v) {
        return v ? 1 << __lg(2 * v - 1) : 1;
    }

    virtual T calculate_root(int N) { }

public:
    virtual vector<T> transform(vector<T> y, bool invert = false) = 0;

    vector<T> linear_convolution(vector<T> a, vector<T> b) {
        const int n = result_length(a.size(), b.size()), n2 = nextpow2(n);
        a.resize(n2);
        b.resize(n2);
        vector<T> fa = transform(move(a)), fb = transform(move(b)), &fc = fa;
        for (int i = 0; i < n2; ++i) fc[i] = fa[i] * fb[i];
        vector<T> c = transform(move(fc), true);
        c.resize(n);
        return move(c);
    }

    vector<T> linear_convolution_power(vector<T> a, long long power, int length = -1) {
        const int n = length < 0 ? result_length_power(a.size(), power) : length, n2 = nextpow2(n);
        a.resize(n2);
        vector<T> fa = transform(move(a)), &fc = fa;
        for (int i = 0; i < n2; ++i) fc[i] = binpow(fa[i], power);
        vector<T> c = transform(move(fc), true);
        c.resize(n);
        return move(c);
    }
};


using namespace std;

template<typename T>
class SumFFT: public FFT<T> {
    int result_length(int first_length, int second_length) {
        return max(first_length + second_length - 1, 0);
    }

    long long result_length_power(long long length, long long power) {
        return max(((length - 1) << power) + 1, 0ll);
    }

protected:
    virtual T calculate_root(int N) = 0;

public:
    vector<T> transform(vector<T> y, bool invert = false) {
        const int N = y.size();
        assert(N == (N&-N));
        vector<int> rev(N);
        for (int i = 1; i < N; ++i) {
            rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? N >> 1 : 0);
            if (rev[i] < i) swap(y[i], y[rev[i]]);
        }
        vector<T> rootni(N / 2);
        for (int n = 2; n <= N; n *= 2) {
            T rootn = calculate_root(n);
            if (invert) {
                rootn = T(1) / rootn;
            }
            rootni[0] = 1;
            for (int i = 1; i < n / 2; ++i) rootni[i] = rootni[i - 1] * rootn;
            for (int left = 0; left != N; left += n) {
                const int mid = left + n / 2;
                for (int i = 0; i < n / 2; ++i) {
                    const T temp = rootni[i] * y[mid + i];
                    y[mid + i] = y[left + i] - temp;
                    y[left + i] += temp;
                }
            }
        }
        if (invert) for (auto &v : y) v /= N;
        return move(y);
    }

    vector<T> bluestein(vector<T> y, bool invert) {
        int n = y.size(), N = 2 * n;
        T rootn = calculate_root(N), inverse_rootn = 1 / rootn;
        if (invert) {
            swap(rootn, inverse_rootn);
        }
        vector<long long> A(n), B(2 * n - 1);
        for (int i = 0; i < n; i++) {
            A[i] = (long long)(y[i] * binpow(rootn, (long long)i * i));
        }
        for (int i = -(n - 1); i < n; i++) {
            B[i + n - 1] = (long long)(binpow(inverse_rootn, (long long)i * i));
        }
        fft::mul(A, B);
        for (int i = 0; i < n; i++) {
            y[i] = binpow(rootn, (long long)i * i) * A[n - 1 + i];
        }
        if (invert) for (auto &v : y) v /= n;
        return move(y);
    }

    vector<T> cyclic_convolution(vector<T> a, vector<T> b) {
        assert(a.size() == b.size());
        int n = a.size();
        vector<T> c = this->linear_convolution(move(a), move(b));
        for (int i = c.size() - 1; i >= n; --i) c[i - n] += c[i];
        c.resize(n);
        return move(c);
    }

    vector<T> cyclic_convolution_power(vector<T> a, long long power, int length = -1) {
        int n = a.size();
        vector<T> c = this->linear_convolution_power(move(a), power, length);
        for (int i = c.size() - 1; i >= n; --i) c[i % n] += c[i];
        c.resize(n);
        return move(c);
    }

    template<typename U>
    vector<T> cyclic_convolution(vector<T> a, vector<T> b) {
        assert(a.size() == b.size());
        int n = a.size();
        vector<T> fa = bluestein(move(a)), fb = bluestein(move(b)), &fc = fa;
        for (int i = 0; i < n; ++i) fc[i] = fa[i] * fb[i];
        vector<T> c = bluestein(move(fc), true);
        return move(c);
    }

    template<typename U>
    vector<T> cyclic_convolution_power(vector<T> a, long long power) {
        int n = a.size();
        vector<T> fa = bluestein(move(a)), &fc = fa;
        for (int i = 0; i < n; ++i) fc[i] = binpow(fa[i], power);
        vector<T> c = transform(move(fc), true);
        return move(c);
    }
};


//
// Created by aryssoncf on 25/10/2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_COMPLEXFFT_HPP
#define JHELPER_EXAMPLE_PROJECT_COMPLEXFFT_HPP

#endif //JHELPER_EXAMPLE_PROJECT_COMPLEXFFT_HPP


#include <cmath>
#include <complex.h>


using namespace std;

template<typename T>
class ComplexFFT: public SumFFT<complex<T>> {
    complex<T> calculate_root(int N) {
        return polar(1.0l, 2 * acosl(-1) / N);
    }
};

using namespace std;

class CProductModulo {

    const static int MOD = 200'003;

    using Mod = ZnConst<MOD>;
    using T = complex<long double>;

    vector<int> get_logs(int root) {
        Mod P = Mod::valueOf(1);
        vector<int> res(MOD);
        res[0] = -1;
        for (int i = 0; i < MOD - 1; i++) {
            res[P.intValue()] = i;
            P *= root;
        }
        return res;
    }

public:
	void solve(std::istream& in, std::ostream& out) {
        int n;
        in >> n;
        vi A(n);
        in >> A;
        int root = find_generator(MOD);
        vi logs = get_logs(root);
        int s = MOD - 1;
        while (s & (s - 1)) {
            s++;
        }
        s *= 2;
        vector<T> aux(s);
        FOR(i, 0, n) {
            if (A[i]) {
                aux[logs[A[i]]] += 1;
            }
        }
        ComplexFFT<long double> sfft;
        aux = sfft.transform(aux, false);
        trav(x, aux) {
            x *= x;
        }
        aux = sfft.transform(aux, true);
        ll res = 0;
        FOR(i, 0, sz(aux)) {
//            if (aux[i].real()) {
//                out << i << ' ' << aux[i] << '\n';
//            }
            res += (ll)(round(aux[i].real())) * binpow(Mod :: valueOf(root), i).intValue();
        }
        trav(x, A) {
            res -= (ll)x * x % MOD;
        }
        res /= 2;
        out << res << '\n';
	}

	void setup() {

    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
	CProductModulo solver;
    solver.setup();
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 58368