#line 2 "nachia\\array\\csr-array.hpp"
#include <utility>
#include <vector>
#include <algorithm>

namespace nachia{

template<class Elem>
class CsrArray{
public:
    struct ListRange{
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        Elem& operator[](int i) const { return begi[i]; }
    };
    struct ConstListRange{
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Elem& operator[](int i) const { return begi[i]; }
    };
private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n+1, 0);
        for(auto& [u,v] : items){ ++buf[u]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.m_list.resize(buf[n]);
        for(int i=(int)items.size()-1; i>=0; i--){
            res.m_list[--buf[items[i].first]] = std::move(items[i].second);
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
        CsrArray res;
        res.m_n = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos = std::move(pos);
        return res;
    }
    ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    int size() const { return m_n; }
    int fullSize() const { return (int)m_list.size(); }
};

} // namespace nachia
#line 3 "nachia\\tree\\centroid-decomposition.hpp"

namespace nachia{

struct CentroidDecomposition {
    int n;
    CsrArray<int> E;
    std::vector<int> cdep;
    std::vector<int> cp;
    std::vector<int> cbfs;
    int maxdep;
    CentroidDecomposition(CsrArray<int> edges) : E(std::move(edges)){
        n = E.size();
        std::vector<int> Z(n, 1);
        {
            std::vector<int> P(n, -1);
            std::vector<int> I = { 0 };
            for(int i=0; i<(int)I.size(); i++){
                int p = I[i];
                for (int e : E[p]) if (P[p] != e) {
                    P[e] = p;
                    I.push_back(e);
                }
            }
            for (int i=n-1; i>=1; i--) Z[P[I[i]]] += Z[I[i]];
        }
        cp.assign(n, -1);
        cdep.assign(n, 0);
        std::vector<std::pair<int, int>> I = { {0,-1} };
        for(int i=0; i<(int)I.size(); i++){
            int s = I[i].first;
            int par = I[i].second;
            while (true) {
                int nx = -1;
                for (int e : E[s]) if (Z[e] * 2 > Z[s]) nx = e;
                if (nx == -1) break;
                Z[s] -= Z[nx];
                Z[nx] += Z[s];
                s = nx;
            }
            cbfs.push_back(s);
            Z[s] = 0;
            if (par != -1) {
                cdep[s] = cdep[par] + 1;
                cp[s] = par;
            }
            for (int e : E[s]) if (Z[e] != 0) {
                I.push_back(std::make_pair(e, s));
            }
        }
        maxdep = 0;
        for (int a : cdep) maxdep = std::max(maxdep, a);
    }

    struct BFSUnit {
        std::vector<int> I;
        std::vector<int> P;
    };
    BFSUnit bfs_layer(int s, int layer) {
        BFSUnit res;
        if (cdep[s] < layer) return res;
        res.I.push_back(s);
        res.P.push_back(-1);
        for(int i=0; i<(int)res.I.size(); i++){
            int p = res.I[i];
            for (int e : E[p]) if (res.P[i] != e) {
                if (cdep[e] < layer) continue;
                res.I.push_back(e);
                res.P.push_back(p);
            }
        }
        return res;
    }
};

} // namespace nachia
#line 4 "nachia\\graph\\graph.hpp"
#include <cassert>
#line 6 "nachia\\graph\\graph.hpp"

namespace nachia{


struct Graph {
public:
    struct Edge{
        int from, to;
        void reverse(){ std::swap(from, to); }
    };
    using Base = std::vector<std::pair<int, int>>;
    Graph(int n = 0, bool undirected = false) : m_n(n), m_e(), m_isUndir(undirected) {}
    Graph(int n, const std::vector<std::pair<int, int>>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){
        m_e.resize(edges.size());
        for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second };
    }
    Graph(int n, const std::vector<Edge>& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {}
    Graph(int n, std::vector<Edge>&& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {}
    int numVertices() const noexcept { return m_n; }
    int numEdges() const noexcept { return int(m_e.size()); }
    int addNode() noexcept { return m_n++; }
    int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; }
    Edge& operator[](int ei) noexcept { return m_e[ei]; }
    const Edge& operator[](int ei) const noexcept { return m_e[ei]; }
    Edge& at(int ei) { return m_e.at(ei); }
    const Edge& at(int ei) const { return m_e.at(ei); }
    auto begin(){ return m_e.begin(); }
    auto end(){ return m_e.end(); }
    auto begin() const { return m_e.begin(); }
    auto end() const { return m_e.end(); }
    bool isUndirected() const noexcept { return m_isUndir; }
    void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); }
    void contract(int newV, const std::vector<int>& mapping){
        assert(numVertices() == int(mapping.size()));
        for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
        for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; }
    }
    std::vector<Graph> induce(int num, const std::vector<int>& mapping) const {
        int n = numVertices();
        assert(n == int(mapping.size()));
        for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
        std::vector<int> indexV(n), newV(num);
        for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
        std::vector<Graph> res; res.reserve(num);
        for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected());
        for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
        return res;
    }
    CsrArray<int> getEdgeIndexArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for(int i=0; i<numEdges(); i++){
            auto e = operator[](i);
            src.emplace_back(e.from, i);
            if(undirected) src.emplace_back(e.to, i);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); }
    CsrArray<int> getAdjacencyArray(bool undirected) const {
        std::vector<std::pair<int, int>> src;
        src.reserve(numEdges() * (undirected ? 2 : 1));
        for(auto e : m_e){
            src.emplace_back(e.from, e.to);
            if(undirected) src.emplace_back(e.to, e.from);
        }
        return CsrArray<int>::Construct(numVertices(), src);
    }
    CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); }
private:
    int m_n;
    std::vector<Edge> m_e;
    bool m_isUndir;
};

} // namespace nachia
#line 4 "nachia\\fps\\formal-power-series-struct.hpp"
#include <string>
#line 6 "nachia\\fps\\formal-power-series-struct.hpp"
#include <iostream>
#line 4 "nachia\\math-modulo\\modulo-primitive-root.hpp"

namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) {
        unsigned long long res = 1, aa = a;
        while(i){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
            i /= 2;
        }
        return res;
    }
    static constexpr bool ExamineVal(unsigned int g){
        unsigned int t = MOD - 1;
        for(unsigned long long d=2; d*d<=t; d++) if(t % d == 0){
            if(powm(g, (MOD - 1) / d) == 1) return false;
            while(t % d == 0) t /= d;
        }
        if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
        return true;
    }
    static constexpr unsigned int GetVal(){
        for(unsigned int x=2; x<MOD; x++) if(ExamineVal(x)) return x;
        return 0;
    }
    static const unsigned int val = GetVal();
};

}
#line 3 "nachia\\math\\combination.hpp"

namespace nachia{

template<class Modint>
class Comb{
private:
    std::vector<Modint> F;
    std::vector<Modint> iF;
public:
    void extend(int newN){
        int prevN = (int)F.size() - 1;
        if(prevN >= newN) return;
        F.resize(newN+1);
        iF.resize(newN+1);
        for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);
        iF[newN] = F[newN].inv();
        for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i);
    }
    Comb(int n = 1){
        F.assign(2, Modint(1));
        iF.assign(2, Modint(1));
        extend(n);
    }
    Modint factorial(int n) const { return F[n]; }
    Modint invFactorial(int n) const { return iF[n]; }
    Modint invOf(int n) const { return iF[n] * F[n-1]; }
    Modint comb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[r] * iF[n-r];
    }
    Modint invComb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[r] * F[n-r];
    }
    Modint perm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[n-r];
    }
    Modint invPerm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[n-r];
    }
    Modint operator()(int n, int r) const { return comb(n,r); }
};

} // namespace nachia
#line 4 "nachia\\misc\\bit-operations.hpp"

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    int res = 0;
    for(int d=32; d>=0; d>>=1) if(x >> d){ res |= d; x >>= d; }
    return res;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return msb_idx(x & -x);
#endif
}

}

#line 2 "nachia\\fps\\ntt-interface.hpp"

namespace nachia {

template<class mint>
struct NttInterface{

template<class Iter>
void Butterfly(Iter, int) const {}

template<class Iter>
void IButterfly(Iter, int) const {}

template<class Iter>
void BitReversal(Iter a, int N) const {
    for(int i=0, j=0; j<N; j++){
        if(i < j) std::swap(a[i], a[j]);
        for(int k = N>>1; k > (i^=k); k>>=1);
    }
}

};

} // namespace nachia
#line 5 "nachia\\fps\\ntt-acl.hpp"
#include <iterator>
#line 8 "nachia\\fps\\ntt-acl.hpp"
#include <array>

namespace nachia{
    
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

template <class mint>
struct NttFromAcl : NttInterface<mint> {

using u32 = unsigned int;
using u64 = unsigned long long;
    
static int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (u32)(n)) x++;
    return x;
}

struct fft_info {
    static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
    static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
    std::array<mint, rank2+1> root;
    std::array<mint, rank2+1> iroot;

    std::array<mint, std::max(0, rank2-1)> rate2;
    std::array<mint, std::max(0, rank2-1)> irate2;

    std::array<mint, std::max(0, rank2-2)> rate3;
    std::array<mint, std::max(0, rank2-2)> irate3;

    fft_info(){
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for(int i=rank2-1; i>=0; i--){
            root[i] = root[i+1] * root[i+1];
            iroot[i] = iroot[i+1] * iroot[i+1];
        }
        mint prod = 1, iprod = 1;
        for(int i=0; i<=rank2-2; i++){
            rate2[i] = root[i+2] * prod;
            irate2[i] = iroot[i+2] * iprod;
            prod *= iroot[i+2];
            iprod *= root[i+2];
        }
        prod = 1; iprod = 1;
        for(int i=0; i<=rank2-3; i++){
            rate3[i] = root[i+3] * prod;
            irate3[i] = iroot[i+3] * iprod;
            prod *= iroot[i+3];
            iprod *= root[i+3];
        }
    }
};

template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;

    int len = 0;
    while(len < h){
        if(h-len == 1){
            int p = 1 << (h-len-1);
            mint rot = 1;
            for(int s=0; s<(1<<len); s++){
                int offset = s << (h-len);
                for(int i=0; i<p; i++){
                    auto l = a[i+offset];
                    auto r = a[i+offset+p] * rot;
                    a[i+offset] = l+r;
                    a[i+offset+p] = l-r;
                }
                if(s+1 != (1<<len)) rot *= info.rate2[LsbIndex(~(u32)(s))];
            }
            len++;
        } else {
            int p = 1 << (h-len-2);
            mint rot = 1, imag = info.root[2];
            for(int s=0; s<(1<<len); s++){
                mint rot2 = rot * rot;
                mint rot3 = rot2 * rot;
                int offset = s << (h-len);
                for(int i=0; i<p; i++){
                    auto mod2 = 1ULL * mint::mod() * mint::mod();
                    auto a0 = 1ULL * a[i+offset].val();
                    auto a1 = 1ULL * a[i+offset+p].val() * rot.val();
                    auto a2 = 1ULL * a[i+offset+2*p].val() * rot2.val();
                    auto a3 = 1ULL * a[i+offset+3*p].val() * rot3.val();
                    auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).val() * imag.val();
                    auto na2 = mod2 - a2;
                    a[i+offset] = a0 + a2 + a1 + a3;
                    a[i+offset+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                    a[i+offset+2*p] = a0 + na2 + a1na3imag;
                    a[i+offset+3*p] = a0 + na2 + (mod2 - a1na3imag);
                }
                if(s+1 != (1<<len)) rot *= info.rate3[LsbIndex(~(u32)(s))];
            }
            len += 2;
        }
    }
}

template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;
    constexpr int MOD = mint::mod();

    int len = h;
    while(len){
        if(len == 1){
            int p = 1 << (h-len);
            mint irot = 1;
            for(int s=0; s<(1<<(len-1)); s++){
                int offset = s << (h-len+1);
                for(int i=0; i<p; i++){
                    auto l = a[i+offset];
                    auto r = a[i+offset+p];
                    a[i+offset] = l+r;
                    a[i+offset+p] = (u64)(MOD + l.val() - r.val()) * irot.val();
                }
                if(s+1 != (1<<(len-1))) irot *= info.irate2[LsbIndex(~(u32)(s))];
            }
            len--;
        } else {
            int p = 1 << (h-len);
            mint irot = 1, iimag = info.iroot[2];
            for(int s=0; s<(1<<(len-2)); s++){
                mint irot2 = irot * irot;
                mint irot3 = irot2 * irot;
                int offset = s << (h-len+2);
                for(int i=0; i<p; i++){
                    auto a0 = 1ULL * a[i+offset+0*p].val();
                    auto a1 = 1ULL * a[i+offset+1*p].val();
                    auto a2 = 1ULL * a[i+offset+2*p].val();
                    auto a3 = 1ULL * a[i+offset+3*p].val();

                    auto a2na3iimag = 1ULL * mint((MOD + a2 - a3) * iimag.val()).val();

                    a[i+offset] = a0 + a1 + a2 + a3;
                    a[i+offset+1*p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
                    a[i+offset+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
                    a[i+offset+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
                }
                if(s+1 != (1<<(len-2))) irot *= info.irate3[LsbIndex(~(u32)(s))];
            }
            len -= 2;
        }
    }
}

};

} // namespace nachia
#line 11 "nachia\\fps\\formal-power-series-struct.hpp"

namespace nachia {

template<class Elem, class NttInst = NttFromAcl<Elem>>
struct FormalPowerSeriesNTT {
public:
    using MyType = FormalPowerSeriesNTT;
    using ElemTy = Elem;
    static constexpr unsigned int MOD = Elem::mod();
    static const NttInst nttInst;
    static const unsigned int zeta = nachia::PrimitiveRoot<MOD>::GetVal();
private:
    using u32 = unsigned int;
    static Elem ZeroElem() noexcept { return Elem(0); }
    static Elem OneElem() noexcept { return Elem(1); }
    static Comb<Elem> comb;
    std::vector<Elem> a;
public:

    int size() const noexcept { return a.size(); }
    Elem& operator[](int x) noexcept { return a[x]; }
    const Elem& operator[](int x) const noexcept { return a[x]; }
    Elem get_coeff(int x) const noexcept { return (x < size()) ? a[x] : ZeroElem(); }
    static Comb<Elem>& GetComb() { return comb; }
    static int BestNttSize(int x) noexcept { assert(x); return 1 << MsbIndex(x*2-1); }

    MyType& removeLeadingZeros(){
        int newsz = size();
        while(newsz && a[newsz-1].val() == 0) newsz--;
        a.resize(newsz);
        if((int)a.capacity() / 4 > newsz) a.shrink_to_fit();
        return *this;
    }

    FormalPowerSeriesNTT(){ a = {  }; }
    FormalPowerSeriesNTT(int new_size) : a(new_size, ZeroElem()) {}
    FormalPowerSeriesNTT(std::vector<Elem>&& src) : a(std::move(src)) {}
    FormalPowerSeriesNTT(const std::vector<Elem>& src) : a(src) {}
    
    MyType& ntt() {
        int N = 1; while (N < (int)size()) N *= 2;
        a.resize(N, ZeroElem());
        nttInst.Butterfly(a.begin(), N);
        return *this;
    }
    MyType& intt() {
        nttInst.IButterfly(a.begin(), a.size());
        Elem invN = Elem(size()).inv();
        for(int i=0; i<size(); i++) a[i] *= invN;
        return *this;
    }
    MyType nttDouble(MyType vanilla) const {
        int n = size();
        assert(n == (n&-n)); // n is a power of 2
        Elem q = Elem::raw(zeta).pow((Elem::mod() - 1) / (n*2));
        Elem qq = Elem::raw(1);
        for(int i=0; i<n; i++){ vanilla[i] *= qq; qq *= q; }
        vanilla.ntt();
        MyType res = clip(0, n, 0, n*2);
        for(int i=0; i<n; i++) res[n+i] = vanilla[i];
        return res;
    }
    MyType nttDouble() const {
        MyType van = clip();
        van.intt();
        return nttDouble(std::move(van));
    }

    // returns [ a[l], a[l+1], a[l+2], ... , a[r-1] ]
    // a[i] = 0 ( i < 0 OR size() <= i )
    MyType getSlice(int l, int r) const {
        if(l >= r) return MyType();
        MyType res(r - l);
        for(int i=l; i<r; i++) res[i-l] = (0 <= i && i < (int)size()) ? a[i] : ZeroElem();
        return res;
    }

    MyType clip(int srcPos = 0, int srcLen = -1, int destPos = 0, int destSize = -1) const {
        int l = std::min((int)size(), srcPos);
        int r = srcLen < 0 ? (int)size() : std::min((int)size(), l + srcLen);
        if(destSize < 0) destSize = r - l + destPos;
        int dr = std::min(r-l, destSize - destPos);
        MyType res(destSize);
        for(int i=0; i<dr; i++) res[destPos+i] = a[l+i];
        return res;
    }

    // upper < 0  ->  upper = lower
    MyType& capSize(int lower, int upper = -1) {
        if(upper < 0) upper = lower;
        if(upper <= (int)size()) a.resize(upper);
        if((int)size() <= lower) a.resize(lower, ZeroElem());
        return *this;
    }

    MyType& mulEach(const MyType& other, size_t maxi = ~(size_t)0){
        maxi = std::min(maxi, (size_t)std::min(size(), other.size()));
        for(size_t i=0; i<maxi; i++) a[i] *= other[i];
        return *this;
    }

    MyType& times(Elem x){
        int n = size();
        for(int i=0; i<n; i++) a[i] *= x;
        return *this;
    }

    MyType& clrRange(int l, int r){
        for(int i=l; i<r; i++) a[i] = 0;
        return *this;
    }

    static MyType convolution(const MyType& a, const MyType& b, int sz = -1){
        if(a.size() <= 30 || b.size() <= 30){
            if(a.size() > 30) return convolution(b,a);
            if(sz < 0) sz = std::max(0, a.size() + b.size() - 1);
            std::vector<Elem> res(sz);
            for(int i=0; i<a.size(); i++) for(int j=0; j<b.size() && i+j<sz; j++) res[i+j] += a[i] * b[j];
            return res;
        }
        int z = a.size() + b.size() - 1;
        int Z = BestNttSize(z);
        if(sz == -1) sz = z;
        MyType ax = a.getSlice(0, Z);
        MyType bx = b.getSlice(0, Z);
        ax.ntt().mulEach(bx.ntt()).intt();
        if(sz != z) ax = ax.clip(0, sz);
        return ax;
    }
    
    //   1
    // ----- = 1 + f + f^2 + f^3 + ...
    //  1-f
    MyType powerSum(int sz) const {
        if (sz == 0) { return {}; }
        int q = std::min((int)sz, 32);
        MyType x = MyType(q);
        x[0] = OneElem();
        for(int i=1; i<q; i++) for(int j=1; j<=std::min(i,(int)a.size()-1); j++) x[i] += x[i-j] * a[j];
        while(x.size() < sz){
            int hN = x.size(), N = hN*2;
            MyType a = x.clip(0, hN, 0, N);
            MyType b = clip(0, N, 0, N);
            a.ntt();
            b.ntt().mulEach(a).intt().clrRange(0,hN).ntt().mulEach(a).intt();
            for(int i=0; i<hN; i++) b[i] = x[i];
            std::swap(b, x);
        }
        if(x.size() != sz) x = x.clip(0, sz);
        return x;
    }

    MyType inv(int sz) const {
        Elem iA0 = a[0].inv();
        MyType xA = clip(0, std::min(sz, size()));
        xA.times(-iA0);
        xA[0] = 0;
        xA = xA.powerSum(sz);
        return xA.times(iA0);
    }
    
    MyType& difference(){
        if(size() == 0) return *this;
        for(int i=0; i+1<size(); i++) a[i] = a[i+1] * Elem::raw(i+1);
        capSize(0, size() - 1);
        return *this;
    }
    MyType& integral(){
        if(size() == 0){
            a.push_back(ZeroElem());
            return *this;
        }
        capSize(size()+1);
        comb.extend(size());
        for(int i=size()-1; i>=1; i--) a[i] = a[i-1] * comb.invOf(i);
        a[0] = ZeroElem();
        return *this;
    }
    
    MyType log(int sz){
        assert(sz != 0);
        assert(a[0].val() == 1);
        return convolution(inv(sz), clip().difference(), sz-1).integral();
    }

    MyType exp(int sz){
        MyType res = MyType(std::vector<Elem>{ OneElem() });
        while(res.size() < sz){
            auto z = res.size();
            res = res.clip(0, z, 0, z*2);
            auto tmp = res.log(z*2);
            tmp[0] = -OneElem();
            for(int i=0; i<z*2 && i<size(); i++) tmp[i] = tmp[i] - a[i];
            auto resntt = res;
            resntt.ntt().mulEach(tmp.ntt()).intt();
            for(int i=z; i<z*2; i++) res[i] = -resntt[i];
        }
        if(sz != res.size()) res = res.clip(0, sz);
        return res;
    }

    MyType& reverse(){ std::reverse(a.begin(), a.end()); return *this; }
    
    MyType pow(unsigned long long k){
        int n = size();
        if(k == 0){ MyType res(n); res[0] = 1; return res; }
        int ctz = 0;
        while(ctz<n && a[ctz].val() == 0) ctz++;
        if((unsigned long long)ctz >= (n-1) / k + 1) return MyType(n);
        MyType res = clip(ctz, n-ctz*k);
        Elem a0 = res[0];
        ctz *= k; n -= ctz;
        return res.times(a0.inv()).log(n).times(Elem(k)).exp(n).times(a0.pow(k)).clip(0, n, ctz);
    }

    auto begin(){ return a.begin(); }
    auto end(){ return a.end(); }
    auto begin() const { return a.begin(); }
    auto end() const { return a.end(); }

    std::string toString(std::string beg = "[ ", std::string delim = " ", std::string en = " ]") const {
        std::string res = beg;
        bool f = false;
        for(auto x : a){ if(f){ res += delim; } f = true; res += std::to_string(x.val()); }
        res += en;
        return res;
    }

    std::vector<Elem> get_vector_moved(){
        std::vector<Elem> res = std::move(a);
        a.clear();
        return res;
    }

    MyType axPlusB(Elem a, Elem b) const {
        auto buf = MyType(size() + 1);
        for(int i=0; i<size(); i++) buf[i] += this->a[i] * b;
        for(int i=0; i<size(); i++) buf[i+1] += this->a[i] * a;
        return buf;
    }

    MyType operator+(const MyType& r) const {
        auto sz = std::max(this->size(), r.size());
        MyType res(sz);
        for(int i=0; i<this->size(); i++) res[i] += this->operator[](i);
        for(int i=0; i<r.size(); i++) res[i] += r[i];
        return res;
    }
    
    MyType operator-(const MyType& r) const {
        auto sz = std::max(this->size(), r.size());
        MyType res(sz);
        for(int i=0; i<this->size(); i++) res[i] += this->operator[](i);
        for(int i=0; i<r.size(); i++) res[i] -= r[i];
        return res;
    }

    MyType operator*(const MyType& r) const {
        auto res = convolution(*this, r);
        return std::move(res.removeLeadingZeros());
    }
    MyType& operator*=(const MyType& r){ (*this) = (*this) * r; return *this; }
    MyType& operator*=(Elem m){ for(size_t i=0; i<a.size(); i++) a[i] *= m; return *this; }
    MyType operator*(Elem m) const { MyType b = *this; b *= m; return b; }

    Elem eval(Elem x) const {
        int z = size();
        Elem res = 0;
        for(int i=z-1; i>=0; i--) res = res * x + a[i];
        return res;
    }
};

template<class Elem, class NttInst> Comb<Elem> FormalPowerSeriesNTT<Elem, NttInst>::comb;
template<class Elem, class NttInst> const NttInst FormalPowerSeriesNTT<Elem, NttInst>::nttInst;

} // namespace nachia

#line 2 "nachia\\math\\ext-gcd.hpp"

#line 6 "nachia\\math\\ext-gcd.hpp"
namespace nachia{

// ax + by = gcd(a,b)
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, y);
}

} // namespace nachia
#line 5 "nachia\\math-modulo\\static-modint.hpp"

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const noexcept { return x; }
    my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; }
    my_type pow(unsigned long long i) const noexcept {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const noexcept { return x; }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

}
#line 2 "nachia\\misc\\fastio.hpp"
#include <cstdio>
#include <cctype>
#include <cstdint>
#line 6 "nachia\\misc\\fastio.hpp"

namespace nachia{

struct CInStream{
private:
	static const unsigned int INPUT_BUF_SIZE = 1 << 17;
	unsigned int p = INPUT_BUF_SIZE;
	static char Q[INPUT_BUF_SIZE];
public:
	using MyType = CInStream;
	char seekChar() noexcept {
		if(p == INPUT_BUF_SIZE){
			size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
			if(len != INPUT_BUF_SIZE) Q[len] = '\0';
			p = 0;
		}
		return Q[p];
	}
	void skipSpace() noexcept { while(isspace(seekChar())) p++; }
	uint32_t nextU32() noexcept {
		skipSpace();
		uint32_t buf = 0;
		while(true){
			char tmp = seekChar();
			if('9' < tmp || tmp < '0') break;
			buf = buf * 10 + (tmp - '0');
			p++;
		}
		return buf;
	}
	int32_t nextI32() noexcept {
		skipSpace();
		if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); }
		return (int32_t)nextU32();
	}
	uint64_t nextU64() noexcept {
		skipSpace();
		uint64_t buf = 0;
		while(true){
			char tmp = seekChar();
			if('9' < tmp || tmp < '0') break;
			buf = buf * 10 + (tmp - '0');
			p++;
		}
		return buf;
	}
	int64_t nextI64() noexcept {
		skipSpace();
		if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); }
		return (int64_t)nextU64();
	}
	char nextChar() noexcept { skipSpace(); char buf = seekChar(); p++; return buf; }
	std::string nextToken(){
		skipSpace();
		std::string buf;
		while(true){
			char ch = seekChar();
			if(isspace(ch) || ch == '\0') break;
			buf.push_back(ch);
			p++;
		}
		return buf;
	}
	MyType& operator>>(unsigned int& dest) noexcept { dest = nextU32(); return *this; }
	MyType& operator>>(int& dest) noexcept { dest = nextI32(); return *this; }
	MyType& operator>>(unsigned long& dest) noexcept { dest = nextU64(); return *this; }
	MyType& operator>>(long& dest) noexcept { dest = nextI64(); return *this; }
	MyType& operator>>(unsigned long long& dest) noexcept { dest = nextU64(); return *this; }
	MyType& operator>>(long long& dest) noexcept { dest = nextI64(); return *this; }
	MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
	MyType& operator>>(char& dest) noexcept { dest = nextChar(); return *this; }
} cin;

struct FastOutputTable{
	char LZ[1000][4] = {};
	char NLZ[1000][4] = {};
	constexpr FastOutputTable(){
		using u32 = uint_fast32_t;
		for(u32 d=0; d<1000; d++){
			LZ[d][0] = ('0' + d / 100 % 10);
			LZ[d][1] = ('0' + d /  10 % 10);
			LZ[d][2] = ('0' + d /   1 % 10);
			LZ[d][3] = '\0';
		}
		for(u32 d=0; d<1000; d++){
			u32 i = 0;
			if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
			if(d >=  10) NLZ[d][i++] = ('0' + d /  10 % 10);
			if(d >=   1) NLZ[d][i++] = ('0' + d /   1 % 10);
			NLZ[d][i++] = '\0';
		}
	}
};

struct COutStream{
private:
	using u32 = uint32_t;
	using u64 = uint64_t;
	using MyType = COutStream;
	static const u32 OUTPUT_BUF_SIZE = 1 << 17;
	static char Q[OUTPUT_BUF_SIZE];
	static constexpr FastOutputTable TB = FastOutputTable();
	u32 p = 0;
	static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }
	static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }
	template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; }
	void next_dig9(u32 x){
		u32 y;
		Fil(y, x, P10(6));
		nextCstr(TB.LZ[y]);
		Fil(y, x, P10(3));
		nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
	}
public:
	void nextChar(char c){
		Q[p++] = c;
		if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }
	}
	void nextEoln(){ nextChar('\n'); }
	void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
	void nextU32(uint32_t x){
		u32 y = 0;
		if(x >= P10(9)){
			Fil(y, x, P10(9));
			nextCstr(TB.NLZ[y]); next_dig9(x);
		}
		else if(x >= P10(6)){
			Fil(y, x, P10(6));
			nextCstr(TB.NLZ[y]);
			Fil(y, x, P10(3));
			nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
		}
		else if(x >= P10(3)){
			Fil(y, x, P10(3));
			nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
		}
		else if(x >= 1) nextCstr(TB.NLZ[x]);
		else nextChar('0');
	}
	void nextI32(int32_t x){
		if(x >= 0) nextU32(x);
		else{ nextChar('-'); nextU32((u32)-x); }
	}
	void nextU64(uint64_t x){
		u32 y = 0;
		if(x >= P10L(18)){
			Fil(y, x, P10L(18));
			nextU32(y);
			Fil(y, x, P10L(9));
			next_dig9(y); next_dig9(x);
		}
		else if(x >= P10L(9)){
			Fil(y, x, P10L(9));
			nextU32(y); next_dig9(x);
		}
		else nextU32(x);
	}
	void nextI64(int64_t x){
		if(x >= 0) nextU64(x);
		else{ nextChar('-'); nextU64((u64)-x); }
	}
	void writeToFile(bool flush = false){
		fwrite(Q, p, 1, stdout);
		if(flush) fflush(stdout);
		p = 0;
	}
	COutStream(){ Q[0] = 0; }
	~COutStream(){ writeToFile(); }
	MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }
	MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }
	MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }
	MyType& operator<<(int tg){ nextI32(tg); return *this; }
	MyType& operator<<(long tg){ nextI64(tg); return *this; }
	MyType& operator<<(long long tg){ nextI64(tg); return *this; }
	MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }
	MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }
	MyType& operator<<(char tg){ nextChar(tg); return *this; }
} cout;

char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];

} // namespace nachia
#line 7 "Main.cpp"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned int;
#define rep(i,n) for(int i=0; i<int(n); i++)

const u32 MOD = 998244353;
using Modint = nachia::StaticModint<MOD>;
using Fps = nachia::FormalPowerSeriesNTT<Modint>;


int N;
vector<Modint> Q;
nachia::CsrArray<int> E;

Modint k0;
vector<Modint> inv_mod;
Fps C;
vector<Fps> nttC;
vector<Modint> ans;


vector<int> bfsbuf_dist;
void get_bfsbuf_dist(nachia::CentroidDecomposition::BFSUnit tree){
    bfsbuf_dist[tree.I.front()] = 0;
    for(int i=1; i<(int)tree.I.size(); i++){
        bfsbuf_dist[tree.I[i]] = bfsbuf_dist[tree.P[i]] + 1;
    }
}

Fps sigma(const Fps& B){
    int n = B.size() + 2;
    if(n >= 10){
        int Z = 1, d = 0;
        while(Z < n){ Z *= 2; d++; }
        Fps revB(Z*2);
        rep(i, B.size()) revB[Z-i] = B[i];
        revB.ntt().mulEach(nttC[d+1]).intt();
        return revB.clip(Z, n);
    }
    Fps ans(n);
    for(int i=0; i<n; i++) for(int j=0; j<(int)B.size(); j++) ans[i] += C[i+j] * B[j];
    return ans;
}

Fps sigma_tree(const nachia::CentroidDecomposition::BFSUnit& tree){
    Fps dist_freq(tree.I.size());
    get_bfsbuf_dist(tree);
    for(int p : tree.I) dist_freq[bfsbuf_dist[p]] += Q[p];
    dist_freq.removeLeadingZeros();
    return sigma(dist_freq);
}


int main() {
    using nachia::cin;
    using nachia::cout;
    cin >> N;
    Q.resize(N);
    rep(i,N) Q[i] = Modint::raw(cin.nextU32());
    {
        nachia::Graph graph(N);
        rep(i,N-1){
            int u,v; cin >> u >> v; u--; v--;
            graph.addEdge(u, v);
        }
        E = graph.getAdjacencyArray(true);
    }
    
    int max_ntt_size_log = 0;
    while((1 << max_ntt_size_log) < N + 6) max_ntt_size_log++;
    max_ntt_size_log++;
    int max_ntt_size = 1 << max_ntt_size_log;

    k0 = 1;
    for(int i=1; i<=N; i++) k0 = k0 * Modint::raw(i);
    k0 = k0 * k0;
    inv_mod.assign(max_ntt_size+1, 1);
    for(int i=2; i<=max_ntt_size; i++) inv_mod[i] = - inv_mod[MOD % i] * (MOD / i);
    C = Fps(max_ntt_size);
    for(int i=0; i<max_ntt_size; i++) C[i] = k0 * inv_mod[i+1] * inv_mod[i+1];

    nttC.resize(max_ntt_size_log+1);
    for(int d=0; d<=max_ntt_size_log; d++){
        nttC[d] = C.clip(0, 1<<d);
        nttC[d].ntt();
    }

    bfsbuf_dist.assign(N, 0);
    ans.assign(N, 0);

    auto centroid_decomposition = nachia::CentroidDecomposition(E);
    for(int s=0; s<N; s++){
        int dep_s = centroid_decomposition.cdep[s];

        auto bfs_s = centroid_decomposition.bfs_layer(s, dep_s);
        Fps sigma_s = sigma_tree(bfs_s);
        
        for(int nx : E[s]) if(centroid_decomposition.cdep[nx] > dep_s){
            nachia::CentroidDecomposition::BFSUnit bfs_nx = centroid_decomposition.bfs_layer(nx, dep_s+1);
            Fps sigma_nx = sigma_tree(bfs_nx);
            for(int p : bfs_nx.I){
                int d = bfsbuf_dist[p] + 1;
                ans[p] += sigma_s[d] - sigma_nx[d+1];
            }
        }

        ans[s] += sigma_s[0];
    }

    rep(p,N) cout << ans[p].val() << "\n";
    return 0;
}