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

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cerr << #a << " = " << a << endl;

template<typename T> void setmax(T& x, T y) {x = max(x, y);}
template<typename T> void setmin(T& x, T y) {x = min(x, y);}

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace IntModulo
{
	const int mod = 1e9 + 7;

	inline int add(int x, int y, int m = mod)
	{
		if (x + y < m)
			return x + y;
		return x + y - m;
	}

	inline int sub(int x, int y, int m = mod)
	{
		if (x >= y)
			return x - y;
		return x - y + m;
	}

	inline int mult(int x, int y, int m = mod)
	{
		return x * (LL) y % m;
	}

	inline int power(int x, int y, int m = mod)
	{
		int r = 1;
		while(y)
		{
			if (y & 1)
				r = mult(r, x, m);
			x = mult(x, x, m);
			y >>= 1;
		}
		
		return r;
	}
	
	inline int inverse(int x, int m = mod)
	{
		return power(x, m - 2, m);
	}
	
	inline void ADD(int& x, int y, int m = mod)
	{
		x += y;
		if (x >= m) x -= m;
	}
	
	inline void SUB(int& x, int y, int m = mod)
	{
		x -= y;
		if (x < 0) x += m;
	}
	
	inline void MULT(int& x, int y, int m = mod)
	{
		x = (x * (LL) y) % m;
	}
};

namespace Combinatorics
{
	using namespace IntModulo;
	
	const int N = 1 << 20;
	int fact[N];
	int inv[N];
	int invFact[N];
	bool inited = false;
	
	inline int C(int n, int k) // binomial C(n, k)
	{
		return n < k ? 0 : mult(fact[n], mult(invFact[k], invFact[n - k]));
	}
	
	inline int H(int n, int k) // number of solution x1 + .. + xn = k
	{
		return C(n + k - 1, k);
	}
	
	void init()
	{
		debug(Combinatorics::N);
		inited = true;
		inv[1] = 1;
		FOR(i, 2, N)
			inv[i] = mult(mod - mod / i, inv[mod % i]);
		
		invFact[0] = fact[0] = 1;
		FOR(i, 1, N)
		{
			fact[i] = mult(i, fact[i - 1]);
			invFact[i] = mult(invFact[i - 1], inv[i]);
		}
	}	
};

using namespace Combinatorics;

namespace FFT
{
	namespace FastNTT998244353
	{
		const int MOD = 998244353;
		 
		struct mod_int {
			int val;
		 
			mod_int(long long v = 0) {
				if (v < 0) v = v % MOD + MOD;
				if (v >= MOD) v %= MOD;
				val = v;
			}
		 
			static int mod_inv(int a, int m = MOD) {
				// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
				int g = m, r = a, x = 0, y = 1;
		 
				while (r != 0) {
					int q = g / r;
					g %= r; swap(g, r);
					x -= q * y; swap(x, y);
				}
		 
				return x < 0 ? x + m : x;
			}
		 
			explicit operator int() const {
				return val;
			}
		 
			mod_int& operator+=(const mod_int &other) {
				val += other.val;
				if (val >= MOD) val -= MOD;
				return *this;
			}
		 
			mod_int& operator-=(const mod_int &other) {
				val -= other.val;
				if (val < 0) val += MOD;
				return *this;
			}
		 
			static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
		#if !defined(_WIN32) || defined(_WIN64)
				return x % m;
		#endif
				// Optimized mod for Codeforces 32-bit machines.
				// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
				unsigned x_high = x >> 32, x_low = (unsigned) x;
				unsigned quot, rem;
				asm("divl %4\n"
					: "=a" (quot), "=d" (rem)
					: "d" (x_high), "a" (x_low), "r" (m));
				return rem;
			}
		 
			mod_int& operator*=(const mod_int &other) {
				val = fast_mod((uint64_t) val * other.val);
				return *this;
			}
		 
			mod_int& operator/=(const mod_int &other) {
				return *this *= other.inv();
			}
		 
			friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
			friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
			friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
			friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
		 
			mod_int& operator++() {
				val = val == MOD - 1 ? 0 : val + 1;
				return *this;
			}
		 
			mod_int& operator--() {
				val = val == 0 ? MOD - 1 : val - 1;
				return *this;
			}
		 
			mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
			mod_int operator--(int) { mod_int before = *this; --*this; return before; }
		 
			mod_int operator-() const {
				return val == 0 ? 0 : MOD - val;
			}
		 
			bool operator==(const mod_int &other) const { return val == other.val; }
			bool operator!=(const mod_int &other) const { return val != other.val; }
		 
			mod_int inv() const {
				return mod_inv(val);
			}
		 
			mod_int pow(long long p) const {
				assert(p >= 0);
				mod_int a = *this, result = 1;
		 
				while (p > 0) {
					if (p & 1)
						result *= a;
		 
					a *= a;
					p >>= 1;
				}
		 
				return result;
			}
		 
			friend ostream& operator<<(ostream &stream, const mod_int &m) {
				return stream << m.val;
			}
		};
		 
		namespace NTT {
			vector<mod_int> roots = {0, 1};
			vector<int> bit_reverse;
			int max_size = -1;
			mod_int root;
		 
			bool is_power_of_two(int n) {
				return (n & (n - 1)) == 0;
			}
		 
			int round_up_power_two(int n) {
				while (n & (n - 1))
					n = (n | (n - 1)) + 1;
		 
				return max(n, 1);
			}
		 
			// 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.
			void bit_reorder(int n, vector<mod_int> &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 find_root() {
				max_size = 1 << __builtin_ctz(MOD - 1);
				root = 2;
		 
				// Find a max_size-th primitive root of MOD.
				while (!(root.pow(max_size) == 1 && root.pow(max_size / 2) != 1))
					root++;
			}
		 
			void prepare_roots(int n) {
				if (max_size < 0)
					find_root();
		 
				assert(n <= max_size);
		 
				if ((int) roots.size() >= n)
					return;
		 
				int length = get_length(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 primitive roots of MOD.
				while (1 << length < n) {
					// z is a 2^(length + 1)-th primitive root of MOD.
					mod_int z = root.pow(max_size >> (length + 1));
		 
					for (int i = 1 << (length - 1); i < 1 << length; i++) {
						roots[2 * i] = roots[i];
						roots[2 * i + 1] = roots[i] * z;
					}
		 
					length++;
				}
			}
		 
			void fft_iterative(int N, vector<mod_int> &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++) {
							mod_int even = values[start + i];
							mod_int odd = values[start + n + i] * roots[n + i];
							values[start + n + i] = even - odd;
							values[start + i] = even + odd;
						}
			}
		 
			const int FFT_CUTOFF = 150;
		 
			vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {
				int n = left.size();
				int m = right.size();
		 
				// Brute force when either n or m is small enough.
				if (min(n, m) < FFT_CUTOFF) {
					const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;
					vector<uint64_t> result(n + m - 1, 0);
		 
					for (int i = 0; i < n; i++)
						for (int j = 0; j < m; j++) {
							result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);
		 
							if (result[i + j] > ULL_BOUND)
								result[i + j] %= MOD;
						}
		 
					for (uint64_t &x : result)
						if (x >= MOD)
							x %= MOD;
		 
					return vector<mod_int>(result.begin(), result.end());
				}
		 
				int N = round_up_power_two(n + m - 1);
				left.resize(N);
				right.resize(N);
		 
				bool equal = left == right;
				fft_iterative(N, left);
		 
				if (equal)
					right = left;
				else
					fft_iterative(N, right);
		 
				mod_int inv_N = mod_int(N).inv();
		 
				for (int i = 0; i < N; i++)
					left[i] *= right[i] * inv_N;
		 
				reverse(left.begin() + 1, left.end());
				fft_iterative(N, left);
				left.resize(n + m - 1);
				return left;
			}
		 
			vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {
				assert(exponent >= 0);
				vector<mod_int> result = {1};
		 
				if (exponent == 0)
					return result;
		 
				for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
					result = mod_multiply(result, result);
		 
					if (exponent >> k & 1)
						result = mod_multiply(result, v);
				}
		 
				return result;
			}
		 
			vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {
				if (polynomials.empty())
					return {1};
		 
				struct compare_size {
					bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {
						return x.size() > y.size();
					}
				};
		 
				priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end());
		 
				while (pq.size() > 1) {
					vector<mod_int> a = pq.top(); pq.pop();
					vector<mod_int> b = pq.top(); pq.pop();
					pq.push(mod_multiply(a, b));
				}
		 
				return pq.top();
			}
		};

	};
	
	namespace FastNTT818937857
	{
		const int MOD = 818937857;
		 
		struct mod_int {
			int val;
		 
			mod_int(long long v = 0) {
				if (v < 0) v = v % MOD + MOD;
				if (v >= MOD) v %= MOD;
				val = v;
			}
		 
			static int mod_inv(int a, int m = MOD) {
				// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
				int g = m, r = a, x = 0, y = 1;
		 
				while (r != 0) {
					int q = g / r;
					g %= r; swap(g, r);
					x -= q * y; swap(x, y);
				}
		 
				return x < 0 ? x + m : x;
			}
		 
			explicit operator int() const {
				return val;
			}
		 
			mod_int& operator+=(const mod_int &other) {
				val += other.val;
				if (val >= MOD) val -= MOD;
				return *this;
			}
		 
			mod_int& operator-=(const mod_int &other) {
				val -= other.val;
				if (val < 0) val += MOD;
				return *this;
			}
		 
			static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
		#if !defined(_WIN32) || defined(_WIN64)
				return x % m;
		#endif
				// Optimized mod for Codeforces 32-bit machines.
				// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
				unsigned x_high = x >> 32, x_low = (unsigned) x;
				unsigned quot, rem;
				asm("divl %4\n"
					: "=a" (quot), "=d" (rem)
					: "d" (x_high), "a" (x_low), "r" (m));
				return rem;
			}
		 
			mod_int& operator*=(const mod_int &other) {
				val = fast_mod((uint64_t) val * other.val);
				return *this;
			}
		 
			mod_int& operator/=(const mod_int &other) {
				return *this *= other.inv();
			}
		 
			friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
			friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
			friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
			friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
		 
			mod_int& operator++() {
				val = val == MOD - 1 ? 0 : val + 1;
				return *this;
			}
		 
			mod_int& operator--() {
				val = val == 0 ? MOD - 1 : val - 1;
				return *this;
			}
		 
			mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
			mod_int operator--(int) { mod_int before = *this; --*this; return before; }
		 
			mod_int operator-() const {
				return val == 0 ? 0 : MOD - val;
			}
		 
			bool operator==(const mod_int &other) const { return val == other.val; }
			bool operator!=(const mod_int &other) const { return val != other.val; }
		 
			mod_int inv() const {
				return mod_inv(val);
			}
		 
			mod_int pow(long long p) const {
				assert(p >= 0);
				mod_int a = *this, result = 1;
		 
				while (p > 0) {
					if (p & 1)
						result *= a;
		 
					a *= a;
					p >>= 1;
				}
		 
				return result;
			}
		 
			friend ostream& operator<<(ostream &stream, const mod_int &m) {
				return stream << m.val;
			}
		};
		 
		namespace NTT {
			vector<mod_int> roots = {0, 1};
			vector<int> bit_reverse;
			int max_size = -1;
			mod_int root;
		 
			bool is_power_of_two(int n) {
				return (n & (n - 1)) == 0;
			}
		 
			int round_up_power_two(int n) {
				while (n & (n - 1))
					n = (n | (n - 1)) + 1;
		 
				return max(n, 1);
			}
		 
			// 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.
			void bit_reorder(int n, vector<mod_int> &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 find_root() {
				max_size = 1 << __builtin_ctz(MOD - 1);
				root = 2;
		 
				// Find a max_size-th primitive root of MOD.
				while (!(root.pow(max_size) == 1 && root.pow(max_size / 2) != 1))
					root++;
			}
		 
			void prepare_roots(int n) {
				if (max_size < 0)
					find_root();
		 
				assert(n <= max_size);
		 
				if ((int) roots.size() >= n)
					return;
		 
				int length = get_length(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 primitive roots of MOD.
				while (1 << length < n) {
					// z is a 2^(length + 1)-th primitive root of MOD.
					mod_int z = root.pow(max_size >> (length + 1));
		 
					for (int i = 1 << (length - 1); i < 1 << length; i++) {
						roots[2 * i] = roots[i];
						roots[2 * i + 1] = roots[i] * z;
					}
		 
					length++;
				}
			}
		 
			void fft_iterative(int N, vector<mod_int> &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++) {
							mod_int even = values[start + i];
							mod_int odd = values[start + n + i] * roots[n + i];
							values[start + n + i] = even - odd;
							values[start + i] = even + odd;
						}
			}
		 
			const int FFT_CUTOFF = 150;
		 
			vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {
				int n = left.size();
				int m = right.size();
		 
				// Brute force when either n or m is small enough.
				if (min(n, m) < FFT_CUTOFF) {
					const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;
					vector<uint64_t> result(n + m - 1, 0);
		 
					for (int i = 0; i < n; i++)
						for (int j = 0; j < m; j++) {
							result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);
		 
							if (result[i + j] > ULL_BOUND)
								result[i + j] %= MOD;
						}
		 
					for (uint64_t &x : result)
						if (x >= MOD)
							x %= MOD;
		 
					return vector<mod_int>(result.begin(), result.end());
				}
		 
				int N = round_up_power_two(n + m - 1);
				left.resize(N);
				right.resize(N);
		 
				bool equal = left == right;
				fft_iterative(N, left);
		 
				if (equal)
					right = left;
				else
					fft_iterative(N, right);
		 
				mod_int inv_N = mod_int(N).inv();
		 
				for (int i = 0; i < N; i++)
					left[i] *= right[i] * inv_N;
		 
				reverse(left.begin() + 1, left.end());
				fft_iterative(N, left);
				left.resize(n + m - 1);
				return left;
			}
		 
			vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {
				assert(exponent >= 0);
				vector<mod_int> result = {1};
		 
				if (exponent == 0)
					return result;
		 
				for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
					result = mod_multiply(result, result);
		 
					if (exponent >> k & 1)
						result = mod_multiply(result, v);
				}
		 
				return result;
			}
		 
			vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {
				if (polynomials.empty())
					return {1};
		 
				struct compare_size {
					bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {
						return x.size() > y.size();
					}
				};
		 
				priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end());
		 
				while (pq.size() > 1) {
					vector<mod_int> a = pq.top(); pq.pop();
					vector<mod_int> b = pq.top(); pq.pop();
					pq.push(mod_multiply(a, b));
				}
		 
				return pq.top();
			}
		};

	};
	
	namespace FastNTT880803841
	{
		const int MOD = 880803841;
		 
		struct mod_int {
			int val;
		 
			mod_int(long long v = 0) {
				if (v < 0) v = v % MOD + MOD;
				if (v >= MOD) v %= MOD;
				val = v;
			}
		 
			static int mod_inv(int a, int m = MOD) {
				// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
				int g = m, r = a, x = 0, y = 1;
		 
				while (r != 0) {
					int q = g / r;
					g %= r; swap(g, r);
					x -= q * y; swap(x, y);
				}
		 
				return x < 0 ? x + m : x;
			}
		 
			explicit operator int() const {
				return val;
			}
		 
			mod_int& operator+=(const mod_int &other) {
				val += other.val;
				if (val >= MOD) val -= MOD;
				return *this;
			}
		 
			mod_int& operator-=(const mod_int &other) {
				val -= other.val;
				if (val < 0) val += MOD;
				return *this;
			}
		 
			static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
		#if !defined(_WIN32) || defined(_WIN64)
				return x % m;
		#endif
				// Optimized mod for Codeforces 32-bit machines.
				// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
				unsigned x_high = x >> 32, x_low = (unsigned) x;
				unsigned quot, rem;
				asm("divl %4\n"
					: "=a" (quot), "=d" (rem)
					: "d" (x_high), "a" (x_low), "r" (m));
				return rem;
			}
		 
			mod_int& operator*=(const mod_int &other) {
				val = fast_mod((uint64_t) val * other.val);
				return *this;
			}
		 
			mod_int& operator/=(const mod_int &other) {
				return *this *= other.inv();
			}
		 
			friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
			friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
			friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
			friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
		 
			mod_int& operator++() {
				val = val == MOD - 1 ? 0 : val + 1;
				return *this;
			}
		 
			mod_int& operator--() {
				val = val == 0 ? MOD - 1 : val - 1;
				return *this;
			}
		 
			mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
			mod_int operator--(int) { mod_int before = *this; --*this; return before; }
		 
			mod_int operator-() const {
				return val == 0 ? 0 : MOD - val;
			}
		 
			bool operator==(const mod_int &other) const { return val == other.val; }
			bool operator!=(const mod_int &other) const { return val != other.val; }
		 
			mod_int inv() const {
				return mod_inv(val);
			}
		 
			mod_int pow(long long p) const {
				assert(p >= 0);
				mod_int a = *this, result = 1;
		 
				while (p > 0) {
					if (p & 1)
						result *= a;
		 
					a *= a;
					p >>= 1;
				}
		 
				return result;
			}
		 
			friend ostream& operator<<(ostream &stream, const mod_int &m) {
				return stream << m.val;
			}
		};
		 
		namespace NTT {
			vector<mod_int> roots = {0, 1};
			vector<int> bit_reverse;
			int max_size = -1;
			mod_int root;
		 
			bool is_power_of_two(int n) {
				return (n & (n - 1)) == 0;
			}
		 
			int round_up_power_two(int n) {
				while (n & (n - 1))
					n = (n | (n - 1)) + 1;
		 
				return max(n, 1);
			}
		 
			// 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.
			void bit_reorder(int n, vector<mod_int> &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 find_root() {
				max_size = 1 << __builtin_ctz(MOD - 1);
				root = 2;
		 
				// Find a max_size-th primitive root of MOD.
				while (!(root.pow(max_size) == 1 && root.pow(max_size / 2) != 1))
					root++;
			}
		 
			void prepare_roots(int n) {
				if (max_size < 0)
					find_root();
		 
				assert(n <= max_size);
		 
				if ((int) roots.size() >= n)
					return;
		 
				int length = get_length(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 primitive roots of MOD.
				while (1 << length < n) {
					// z is a 2^(length + 1)-th primitive root of MOD.
					mod_int z = root.pow(max_size >> (length + 1));
		 
					for (int i = 1 << (length - 1); i < 1 << length; i++) {
						roots[2 * i] = roots[i];
						roots[2 * i + 1] = roots[i] * z;
					}
		 
					length++;
				}
			}
		 
			void fft_iterative(int N, vector<mod_int> &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++) {
							mod_int even = values[start + i];
							mod_int odd = values[start + n + i] * roots[n + i];
							values[start + n + i] = even - odd;
							values[start + i] = even + odd;
						}
			}
		 
			const int FFT_CUTOFF = 150;
		 
			vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {
				int n = left.size();
				int m = right.size();
		 
				// Brute force when either n or m is small enough.
				if (min(n, m) < FFT_CUTOFF) {
					const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;
					vector<uint64_t> result(n + m - 1, 0);
		 
					for (int i = 0; i < n; i++)
						for (int j = 0; j < m; j++) {
							result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);
		 
							if (result[i + j] > ULL_BOUND)
								result[i + j] %= MOD;
						}
		 
					for (uint64_t &x : result)
						if (x >= MOD)
							x %= MOD;
		 
					return vector<mod_int>(result.begin(), result.end());
				}
		 
				int N = round_up_power_two(n + m - 1);
				left.resize(N);
				right.resize(N);
		 
				bool equal = left == right;
				fft_iterative(N, left);
		 
				if (equal)
					right = left;
				else
					fft_iterative(N, right);
		 
				mod_int inv_N = mod_int(N).inv();
		 
				for (int i = 0; i < N; i++)
					left[i] *= right[i] * inv_N;
		 
				reverse(left.begin() + 1, left.end());
				fft_iterative(N, left);
				left.resize(n + m - 1);
				return left;
			}
		 
			vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {
				assert(exponent >= 0);
				vector<mod_int> result = {1};
		 
				if (exponent == 0)
					return result;
		 
				for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
					result = mod_multiply(result, result);
		 
					if (exponent >> k & 1)
						result = mod_multiply(result, v);
				}
		 
				return result;
			}
		 
			vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {
				if (polynomials.empty())
					return {1};
		 
				struct compare_size {
					bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {
						return x.size() > y.size();
					}
				};
		 
				priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end());
		 
				while (pq.size() > 1) {
					vector<mod_int> a = pq.top(); pq.pop();
					vector<mod_int> b = pq.top(); pq.pop();
					pq.push(mod_multiply(a, b));
				}
		 
				return pq.top();
			}
		};

	};
	
	const int mod[] = {998244353, 818937857, 880803841};
	
	__int128 r[3][3];
	
	__int128 restore(vector<int> a)
	{
		__int128 x[3];		
		FOR(i, 0, 3)
		{
			x[i] = a[i];
			FOR(j, 0, i)
			{
				x[i] = (x[i] - x[j]) * r[j][i] % mod[i];		 
				if (x[i] < 0)  x[i] += mod[i];
			}
		}
		
		__int128 res = 0;
		res += x[0];
		res += x[1] * mod[0];
		res += x[2] * mod[0] * mod[1];
		return res;
	}
	
	template<typename T>
	void multiply(const vector<T>& A, vector<T>& B, T* __restrict C)
	{
		vector<int> res[3];
		{
			vector<FastNTT998244353::mod_int> a(SZ(A));
			FOR(j, 0, SZ(a)) a[j] = A[j] % mod[0];
			vector<FastNTT998244353::mod_int> b(SZ(B));
			FOR(j, 0, SZ(b)) b[j] = B[j] % mod[0];
			
			auto res0 = FastNTT998244353::NTT::mod_multiply(a, b);
			res[0].assign(SZ(A) + SZ(B) + 1, 0);
			FOR(j, 0, SZ(res0)) res[0][j] = (int)res0[j];
		}
		
		{
			vector<FastNTT818937857::mod_int> a(SZ(A));
			FOR(j, 0, SZ(a)) a[j] = A[j] % mod[1];
			vector<FastNTT818937857::mod_int> b(SZ(B));
			FOR(j, 0, SZ(b)) b[j] = B[j] % mod[1];
			
			auto res1 = FastNTT818937857::NTT::mod_multiply(a, b);
			res[1].assign(SZ(A) + SZ(B) + 1, 0);
			FOR(j, 0, SZ(res1)) res[1][j] = (int)res1[j];
		}
		
		{
			vector<FastNTT880803841::mod_int> a(SZ(A));
			FOR(j, 0, SZ(a)) a[j] = A[j] % mod[2];
			vector<FastNTT880803841::mod_int> b(SZ(B));
			FOR(j, 0, SZ(b)) b[j] = B[j] % mod[2];
			
			auto res2 = FastNTT880803841::NTT::mod_multiply(a, b);
			res[2].assign(SZ(A) + SZ(B) + 1, 0);
			FOR(j, 0, SZ(res2)) res[2][j] = (int)res2[j];
		}
		
		FOR(i, 0, 3) FOR(j, 0, 3) if (i != j)
			r[i][j] = power(mod[i], mod[j] - 2, mod[j]);
		
		FOR(i, 0, SZ(A) + SZ(B) + 1)
			C[i] = restore({res[0][i], res[1][i], res[2][i]});
	}
};

const int M = 1 << 20;
__int128 c[M];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	Combinatorics::init();
	
	int n, m, k;
	cin >> n >> m >> k;
	n--;
	int ans = 0;
	vector<__int128> a(m + 1), b(k + 1);
	FOR(i, 0, m + 1) a[i] = invFact[i];
	FOR(i, 0, k + 1) b[i] = invFact[i];
	FFT::multiply(a, b, c);
		
	FOR(t, 0, m + k + 1)		
		ADD(ans, mult(fact[t], mult(c[t] % mod, mult(C(n + t, t), power(3, m + k - t)))));
	
	cout << ans << endl;
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



Measured memory_bytes: 76072