// {{{ y0105w49 template 24K21
// hi mom
#ifndef NULL
#ifdef __GNUC__
#ifndef __clang__
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>
#define EXTS
#else
#ifdef ARST
#include <bits/clang++.h>
#else
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
// #include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
// #include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
// #include <stop_token>
#include <semaphore>
// #include <source_location>
// #include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
// #include <expected>
// #include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif
#endif
#endif
#else
#error "unsupported"
#endif
#endif
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
	template<typename C> struct is_iterable {
		template<class T> static long check(...);
		template<class T> static char check(int,typename T::const_iterator = C().end());
		enum {
			value = sizeof(check<C>(0)) == sizeof(char),
			neg_value = sizeof(check<C>(0)) != sizeof(char)
		};
	};
	template<class T> struct _gbd3C;
	template<class T> ostream &_gbd3(ostream &os,const T &x) { return _gbd3C<T>::call(os,x); }
	template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'<<x<<'"'; }
	template<> ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'<<x<<'"'; }
	template<class T> ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); }
	template<class A,class B> ostream &_gbd4(ostream &os,const pair<A,B> &p) {
		_gbd3(os<<'(',p.first);
		_gbd3(os<<',',p.second);
		return os<<')';
	}
	template<class T,size_t N> struct _gbd4_tupleC {
		static void call(ostream &os,const T &t) {
			_gbd4_tupleC<T,N-1>::call(os,t);
			os<<','<<get<N-1>(t);
		}
	};
	template<class T> struct _gbd4_tupleC<T,1> {
		static void call(ostream &os,const T &t) { os<<get<0>(t); }
	};
	template<typename... Types> ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
		os<<'(';
		_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
		return os<<')';
	}
	template<> ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
	template<class T> ostream &_gbd4(ostream &os,const T &x) {
		return os<<x;
	}
	template<class T> struct _gbd3C {
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
			os<<"{";
			bool ff=0;
			for(const auto &E:V) _gbd3_5<decltype(E)>(ff?os<<",":os,E), ff=1;
			return os<<"}";
		}
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
			return _gbd4(os,x);
		}
	};
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
	ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
	template<typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
		return _gbd2(os<<(fi?"":"  ")<<x,0,nm+1,args...);
	}
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
		return _gbd2(_gbd3<T>(os<<(fi?"":"  ")<<*nm<<"=",x),0,nm+1,args...);
	}
	vector<string> split(string s) {
		vector<string> Z;
		string z="";
		s+=',';
		int dep=0;
		for(char c:s) {
			if(c==',' && !dep) Z.push_back(z),z="";
			else z+=c;
			if(c=='(' || c=='{' || c=='[') ++dep;
			if(c==')' || c=='}' || c==']') --dep;
		}
		return Z;
	}
	template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
		return _gbd2(os,1,split(nm).begin(),args...);
	}
	template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
		ostringstream oss;
		_gbd2(oss,1,split(nm).begin(),args...);
		return oss.str();
	}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
	Fun _fun;
	template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
	template<typename... Args> decltype(auto) operator()(Args&&... args) {
		return _fun(ref(*this),forward<Args>(args)...);
	}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
	return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) (v).begin(),(v).end()
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> T &smin(T &x,const T &y) { return y<x?x=y:x; }
template<class T> T &smax(T &x,const T &y) { return y>x?x=y:x; }
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
template<class T> bool cinb(const T &x,const T &l,const T &r) { return l<=r?l<=x&&x<=r:l<=x||x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
template<template<class> class C,class T> T popv(C<T> &v) { T z=v.back(); v.pop_back(); return z; }
template<template<class> class C,class T> T popq(C<T> &v) { T z=v.front(); v.pop(); return z; }
template<template<class> class C,class T> T pops(C<T> &v) { T z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class,class> class C,class K,class V> pair<K,V> popm(C<K,V> &v) { pair<K,V> z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class> class C,class T> void erase1(C<T> &v,const T &x) { v.erase(v.find(x)); }
template<template<class> class C,class T> int lbi(C<T> &v,const T &x) { return int(lower_bound(all(v),x)-v.begin()); }
template<template<class> class C,class T> int findi(C<T> &v,const T &x) { auto it=lower_bound(all(v),x); return it!=v.end()&&*it==x?int(it-v.begin()):-1; }
template<class V> int sortu(V &v) { sort(all(v)); int z=int(unique(all(v))-v.begin()); v.resize(z); return z; }
template<typename T,typename... Args> T tee(T (*f)(Args... args),Args&&... args) { T z=f(forward<Args>(args)...); cout<<z<<endl; return z; }
template<typename... Args> void tee(void (*f)(Args... args),Args&&... args) { f(forward<Args>(args)...); }
#ifdef EXTS
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
#endif
constexpr int e0=1, e1=10, e2=100, e3=1000;
constexpr int e4=10*e3, e5=100*e3, e6=1000*e3;
constexpr int e7=10*e6, e8=100*e6, e9=1000*e6;
constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9;
constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12;
constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15;
constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18;
constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
using uint=unsigned int;
using ushort=unsigned short;
using uchar=char;
using ld=long double;
#ifdef EXTS
using lld=__float128;
#endif
long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) (assert(!inp),_rand(igen,__VA_ARGS__))
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution<int>(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { DBG=1; dbgt("gg (early)",seed); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
	arg1=0,args={argv,argv+argc};
	if(sz(args)>1) {
		if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
		else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
		else arg1=stoi(args[1]);
	}
	inp=!arg1;
	if(JO && getenv("EMACS")) EMACS=1;
	dbgt(arg1,seed,args);
	#ifdef QUIET
	DBG=0;
	#endif
	MAIN();
	DBG=1;
	dbgt("gg;wp",seed);
	return 0;
}
constexpr int inf=e9+99;
constexpr ll linf=1LL*e9*e9+99;
#if __cplusplus >= 202002L
constexpr long double U_03C4__ld=2*numbers::pi_v<long double>;
#else
const long double U_03C4__ld=2*acosl(-1);
#endif
#define U_03C4_ ((flt)U_03C4__ld)
constexpr long double U_03B5__ld=1e-8l;
#define U_03B5_ ((flt)U_03B5__ld)
// }}}
using flt=double; //CARE
constexpr int P=998'244'353;

Wpush("conversion");
Wpush("float-conversion");

template<typename float_t>
struct fast_complex {
    // credit to neal
    float_t x, y;

    fast_complex(float_t _x = 0, float_t _y = 0) : x(_x), y(_y) {}

    float_t real() const {
        return x;
    }

    void real(float_t _x) {
        x = _x;
    }

    float_t imag() const {
        return y;
    }

    void imag(float_t _y) {
        y = _y;
    }

    fast_complex<float_t>& operator+=(const fast_complex<float_t> &other) {
        x += other.x;
        y += other.y;
        return *this;
    }

    fast_complex<float_t>& operator-=(const fast_complex<float_t> &other) {
        x -= other.x;
        y -= other.y;
        return *this;
    }

    fast_complex<float_t> operator+(const fast_complex<float_t> &other) const {
        return fast_complex<float_t>(*this) += other;
    }

    fast_complex<float_t> operator-(const fast_complex<float_t> &other) const {
        return fast_complex<float_t>(*this) -= other;
    }

    fast_complex<float_t> operator*(const fast_complex<float_t> &other) const {
        return {x * other.x - y * other.y, x * other.y + other.x * y};
    }
};

template<typename float_t>
fast_complex<float_t> fast_conj(const fast_complex<float_t> &c) {
    return {c.x, -c.y};
}

template<typename float_t>
fast_complex<float_t> fast_polar(float_t magnitude, float_t angle) {
    return {magnitude * cos(angle), magnitude * sin(angle)};
}

template<typename float_t>
ostream& operator<<(ostream &stream, const fast_complex<float_t> &c) {
    return stream << '(' << c.x << ", " << c.y << ')';
}


namespace FFT {
    typedef double float_t;
    const float_t ONE = 1;
    const float_t PI = acos(-ONE);

    vector<fast_complex<float_t>> roots;
    vector<int> bit_reverse;

    bool is_power_of_two(int n) {
        return (n & (n - 1)) == 0;
    }

    int round_up_power_two(int n) {
        assert(n > 0);

        while (n & (n - 1))
            n = (n | (n - 1)) + 1;

        return n;
    }

    // Given n (a power of two), finds k such that n == 1 << k.
    int get_length(int n) {
        assert(is_power_of_two(n));
        return __builtin_ctz(n);
    }

    // Rearranges the indices to be sorted by lowest bit first, then second lowest, etc., rather than highest bit first.
    // This makes even-odd div-conquer much easier.
    template<typename fast_complex_array>
    void bit_reorder(int n, fast_complex_array &&values) {
        if ((int) bit_reverse.size() != n) {
            bit_reverse.assign(n, 0);
            int length = get_length(n);

            for (int i = 0; i < n; i++)
                bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
        }

        for (int i = 0; i < n; i++)
            if (i < bit_reverse[i])
                swap(values[i], values[bit_reverse[i]]);
    }

    void prepare_roots(int n) {
        if ((int) roots.size() >= n)
            return;

        if (roots.empty())
            roots = {{0, 0}, {1, 0}};

        int length = get_length((int)roots.size());
        roots.resize(n);

        // The roots array is set up such that for a given power of two n >= 2, roots[n / 2] through roots[n - 1] are
        // the first half of the n-th roots of unity.
        while (1 << length < n) {
            double min_angle = 2 * PI / (1 << (length + 1));

            for (int i = 0; i < 1 << (length - 1); i++) {
                int index = (1 << (length - 1)) + i;
                roots[2 * index] = roots[index];
                roots[2 * index + 1] = fast_polar(ONE, min_angle * (2 * i + 1));
            }

            length++;
        }
    }

    template<typename fast_complex_array>
    void fft_recursive(int n, fast_complex_array &&values, int depth = 0) {
        if (n <= 1)
            return;

        if (depth == 0) {
            assert(is_power_of_two(n));
            prepare_roots(n);
            bit_reorder(n, values);
        }

        n /= 2;
        fft_recursive(n, values, depth + 1);
        fft_recursive(n, values + n, depth + 1);

        for (int i = 0; i < n; i++) {
            const fast_complex<float_t> &even = values[i];
            fast_complex<float_t> odd = values[n + i] * roots[n + i];
            values[n + i] = even - odd;
            values[i] = even + odd;
        }
    }

    // Iterative version of fft_recursive above.
    template<typename fast_complex_array>
    void fft_iterative(int N, fast_complex_array &&values) {
        assert(is_power_of_two(N));
        prepare_roots(N);
        bit_reorder(N, values);

        for (int n = 1; n < N; n *= 2)
            for (int start = 0; start < N; start += 2 * n)
                for (int i = 0; i < n; i++) {
                    const fast_complex<float_t> &even = values[start + i];
                    fast_complex<float_t> odd = values[start + n + i] * roots[n + i];
                    values[start + n + i] = even - odd;
                    values[start + i] = even + odd;
                }
    }

    inline fast_complex<float_t> extract(int N, const vector<fast_complex<float_t>> &values, int index, int side) {
        if (side == -1) {
            // Return the product of 0 and 1.
            int other = (N - index) & (N - 1);
            return (fast_conj(values[other] * values[other]) - values[index] * values[index]) * fast_complex<float_t>(0, 0.25);
        }

        int other = (N - index) & (N - 1);
        int sign = side == 0 ? +1 : -1;
        fast_complex<float_t> multiplier = side == 0 ? fast_complex<float_t>(0.5, 0) : fast_complex<float_t>(0, -0.5);
        return multiplier * fast_complex<float_t>(values[index].real() + values[other].real() * sign,
                                             values[index].imag() - values[other].imag() * sign);
    }

    void invert_fft(int N, vector<fast_complex<float_t>> &values) {
        assert(N >= 2);

        for (int i = 0; i < N; i++)
            values[i] = fast_conj(values[i]) * (ONE / N);

        for (int i = 0; i < N / 2; i++) {
            fast_complex<float_t> first = values[i] + values[N / 2 + i];
            fast_complex<float_t> second = (values[i] - values[N / 2 + i]) * roots[N / 2 + i];
            values[i] = first + second * fast_complex<float_t>(0, 1);
        }

        fft_recursive(N / 2, values.begin());

        for (int i = N - 1; i >= 0; i--)
            values[i] = i % 2 == 0 ? values[i / 2].real() : values[i / 2].imag();
    }

    const int FFT_CUTOFF = 150;
    const double SPLIT_CUTOFF = 2e15;
    const int SPLIT_BASE = 1 << 15;

    template<typename T_out, typename T_in>
    vector<T_out> square(const vector<T_in> &input) {
        int n = input.size();

        // Brute force when n is small enough.
        if (n < 1.5 * FFT_CUTOFF) {
            vector<T_out> result(2 * n - 1);

            for (int i = 0; i < n; i++) {
                result[2 * i] += (T_out) input[i] * input[i];

                for (int j = i + 1; j < n; j++)
                    result[i + j] += (T_out) 2 * input[i] * input[j];
            }

            return result;
        }

        int N = round_up_power_two(n);
        assert(N >= 2);
        prepare_roots(2 * N);
        vector<fast_complex<float_t>> values(N, 0);

        for (int i = 0; i < n; i += 2)
            values[i / 2] = fast_complex<float_t>(input[i], i + 1 < n ? input[i + 1] : 0);

        fft_iterative(N, values.begin());

        for (int i = 0; i <= N / 2; i++) {
            int j = (N - i) & (N - 1);
            fast_complex<float_t> even = extract(N, values, i, 0);
            fast_complex<float_t> odd = extract(N, values, i, 1);
            fast_complex<float_t> aux = even * even + odd * odd * roots[N + i] * roots[N + i];
            fast_complex<float_t> tmp = even * odd;
            values[i] = aux - fast_complex<float_t>(0, 2) * tmp;
            values[j] = fast_conj(aux) - fast_complex<float_t>(0, 2) * fast_conj(tmp);
        }

        for (int i = 0; i < N; i++)
            values[i] = fast_conj(values[i]) * (ONE / N);

        fft_recursive(N, values.begin());
        vector<T_out> result(2 * n - 1);

        for (int i = 0; i < (int) result.size(); i++) {
            float_t value = i % 2 == 0 ? values[i / 2].real() : values[i / 2].imag();
            result[i] = is_integral<T_out>::value ? round(value) : value;
        }

        return result;
    }

    template<typename T_out, typename T_in>
    vector<T_out> multiply(const vector<T_in> &left, const vector<T_in> &right) {
        if (left == right)
            return square<T_out>(left);

        int n = left.size();
        int m = right.size();

        // Brute force when either n or m is small enough.
        if (min(n, m) < FFT_CUTOFF) {
            vector<T_out> result(n + m - 1);

            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    result[i + j] += (T_out) left[i] * right[j];

            return result;
        }

        int N = round_up_power_two(n + m - 1);
        vector<fast_complex<float_t>> values(N, 0);

        for (int i = 0; i < n; i++)
            values[i].real(left[i]);

        for (int i = 0; i < m; i++)
            values[i].imag(right[i]);

        fft_iterative(N, values.begin());

        for (int i = 0; i <= N / 2; i++) {
            int j = (N - i) & (N - 1);
            fast_complex<float_t> product_i = extract(N, values, i, -1);
            values[i] = product_i;
            values[j] = fast_conj(product_i);
        }

        invert_fft(N, values);
        vector<T_out> result(n + m - 1);

        for (int i = 0; i < (int) result.size(); i++)
            result[i] = is_integral<T_out>::value ? round(values[i].real()) : values[i].real();

        return result;
    }

    template<typename T>
    vector<T> mod_multiply(const vector<T> &left, const vector<T> &right, T mod, bool split = false) {
        int n = left.size();
        int m = right.size();

        for (int i = 0; i < n; i++)
            assert(0 <= left[i] && left[i] < mod);

        for (int i = 0; i < m; i++)
            assert(0 <= right[i] && right[i] < mod);

        // Brute force when either n or m is small enough. Brute force up to higher values when split = true.
        if (min(n, m) < (split ? 2 : 1) * FFT_CUTOFF) {
            const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) mod * mod;
            vector<uint64_t> result(n + m - 1);

            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) {
                    result[i + j] += (uint64_t) left[i] * right[j];

                    if (result[i + j] > ULL_BOUND)
                        result[i + j] %= mod;
                }

            for (int i = 0; i < (int) result.size(); i++)
                if (result[i] >= (uint64_t) mod)
                    result[i] %= mod;

            return vector<T>(result.begin(), result.end());
        }

        if (!split) {
            const vector<uint64_t> &product = multiply<uint64_t>(left, right);
            vector<T> result(n + m - 1);

            for (int i = 0; i < (int) result.size(); i++)
                result[i] = product[i] % mod;

            return result;
        }

        int N = round_up_power_two(n + m - 1);
        vector<fast_complex<float_t>> left_fft(N, 0), right_fft(N, 0);

        for (int i = 0; i < n; i++) {
            left_fft[i].real(left[i] % SPLIT_BASE);
            left_fft[i].imag(left[i] / SPLIT_BASE);
        }

        fft_iterative(N, left_fft.begin());

        if (left == right) {
            copy(left_fft.begin(), left_fft.end(), right_fft.begin());
        } else {
            for (int i = 0; i < m; i++) {
                right_fft[i].real(right[i] % SPLIT_BASE);
                right_fft[i].imag(right[i] / SPLIT_BASE);
            }

            fft_iterative(N, right_fft.begin());
        }

        vector<fast_complex<float_t>> product(N);
        vector<T> result(n + m - 1);

        for (int exponent = 0; exponent <= 2; exponent++) {
            uint64_t multiplier = 1;

            for (int k = 0; k < exponent; k++)
                multiplier = multiplier * SPLIT_BASE % mod;

            fill(product.begin(), product.end(), 0);

            for (int x = 0; x < 2; x++)
                for (int y = 0; y < 2; y++)
                    if (x + y == exponent)
                        for (int i = 0; i < N; i++)
                            product[i] += extract(N, left_fft, i, x) * extract(N, right_fft, i, y);

            invert_fft(N, product);

            for (int i = 0; i < (int) result.size(); i++) {
                uint64_t value = round(product[i].real());
                result[i] = (result[i] + value % mod * multiplier) % mod;
            }
        }

        return result;
    }
}

Wpop;
Wpop;

void mul(vector<int> &a,const vector<int> &b) {
	vector<int64_t> A(all(a)),B(all(b));
	vector<int64_t> z=FFT::mod_multiply(A,B,(int64_t)P,true);
	a.resize(sz(z));
	for(int i=0;i<sz(z);i++) a[i]=(int)z[i];
}

void reduce(vector<vector<int>> &v) {
	assert(sz(v)>=1);
	for(;sz(v)>1;) {
		int h=(sz(v)+1)/2;
		for(;sz(v)>h;) mul(v[sz(v)-1-h],v.back()), v.pop_back();
	}
	assert(sz(v)==1);
}

const int N=200<<10;
bool tok[N];
vector<int> fadj[N],radj[N];

array<int,3> f(int u,int p=-1) {
	vector<vector<int>> fws={{1}},rvs={{1}};
	for(int v:fadj[u]) if(v!=p) {
			auto z=f(v,u);
			fws.pb({z[1],z[2]});
		}
	for(int v:radj[u]) if(v!=p) {
			auto z=f(v,u);
			rvs.pb({z[1],z[0]});
		}

	dbg(u,p);
	dbg(fws);
	dbg(rvs);
	reduce(fws);
	reduce(rvs);
	vector<int> FW=fws[0],RV=rvs[0];
	dbg(FW);
	dbg(RV);

	array<int,3> zz;
	for(int d:{-1,0,1}) {
		int z=0;
		for(int end:{0,1}) {
			int o=d+(tok[u]-end);
			for(int i=0;i<sz(FW);i++) {
				int j=i-o;
				if(j<0 || j>=sz(RV)) continue;
				z=int((z+1LL*FW[i]*RV[j])%P);
			}
		}
		zz[d+1]=z;
	}
	dbg(zz);
	dbg("");
	return zz;
}


auto solve() { /* CURSOR START */
	int n; ine(n,arg1);
	if(n>20) DBG=0;
	if(inp) { string s; cin>>s; forenum(i,char c:s) if(c=='S') tok[i+1]=1; }
	else for(int i=1;i<=n;i++) tok[i]=irand(.5);
	for(int i=2;i<=n;i++) {
		int u,v; ine(u,i), inr(v,i-1);
		if(!inp) if(irand(.5)) swap(u,v);
		fadj[u].pb(v);
		radj[v].pb(u);
	}
	return f(1)[1];
}



void _main() { int NTC=1;
	// ine(NTC,5);
	for(int TC=1;TC<=NTC;TC++) {
		// cout<<"Case #"<<TC<<": ";
		tee(solve);
	}
	if(JO&&inp) assert((cin>>ws).eof());
}