代码

#include <algorithm>
#include <cstring>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
size_t big_int_c2i[256][256];
bool big_int_c2i_sat[256];
char big_int_i2c(size_t a) {
	if (a <= 9) {
		return '0' + a;
	} else if (a <= 35) {
		return 'A' + a - 10;
	} else /* if (a <= 62) */ {
		return 'a' + a - 36;
	}
}
size_t default_radix = 0;
struct big_int_radix_setter_t {
	big_int_radix_setter_t() {}
	big_int_radix_setter_t(size_t new_radix) {
		if (new_radix == default_radix) return;
		default_radix = new_radix;
		if (big_int_c2i_sat[default_radix]) return;
		big_int_c2i_sat[default_radix] = true;
		memset(big_int_c2i, -1, sizeof(big_int_c2i));
		if (new_radix <= 10) {
			for (size_t i = 0; i < new_radix; i++) {
				big_int_c2i[new_radix][i + '0'] = i;
			}
		} else if (new_radix <= 36) {
			for (size_t i = 0; i < 10; i++) {
				big_int_c2i[new_radix][i + '0'] = i;
			}
			for (size_t i = 0; i < new_radix - 10; i++) {
				big_int_c2i[new_radix][i + 'A'] = i + 10;
				big_int_c2i[new_radix][i + 'a'] = i + 10;
			}
		} else /* if (new_radix <= 62) */ {
			for (size_t i = 0; i < 10; i++) {
				big_int_c2i[new_radix][i + '0'] = i;
			}
			for (size_t i = 0; i < new_radix - 10; i++) {
				big_int_c2i[new_radix][i + 'A'] = i + 10;
			}
			for (size_t i = 0; i < new_radix - 36; i++) {
				big_int_c2i[new_radix][i + 'a'] = i + 36;
			}
		}
	}
	big_int_radix_setter_t operator()(size_t new_radix) {
		return big_int_radix_setter_t(new_radix);
	}
} set_radix;
const long long big_int_NTT_mod = 2013265921ll;
const long long big_int_NTT_g = 31ll;
struct NTT_calculator {
	size_t k, *rev;
	long long *o;
	NTT_calculator(size_t K)
		: k(K),
		  rev(new size_t[size_t(1) << K]),
		  o(new long long[size_t(1) << K]) {
		rev[0] = 0;
		for (size_t i = 1; i < (size_t(1) << k); i++) {
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
		}
		// cout << std::vector(rev, rev + (size_t(1) << K)) << endl;
	}
	~NTT_calculator() {
		delete[] rev;
		delete[] o;
	}
	inline void bit_reverse(long long *A) {
		for (size_t i = 0; i < (size_t(1) << k); i++) {
			if (i < rev[i]) {
				A[i] ^= A[rev[i]] ^= A[i] ^= A[rev[i]];
			}
		}
	}
	long long quickpower(long long a, size_t b) {
		a %= big_int_NTT_mod;
		long long c = 1;
		while (b) {
			if (b & 1) {
				c *= a;
				c %= big_int_NTT_mod;
			}
			a *= a;
			a %= big_int_NTT_mod;
			b >>= 1;
		}
		return c;
	}
	inline void NTT(long long *A, const long long omega, long long *ANS) {
		size_t n = size_t(1) << k;
		for (size_t i = 0; i < n; i++) {
			ANS[i] = A[i] % big_int_NTT_mod;
		}
		bit_reverse(ANS);
		o[0] = 1ll;
		for (size_t i = 1; i < n; i++) {
			o[i] = o[i - 1] * omega % big_int_NTT_mod;
		}
		long long F_o; // polynome result of odd power
		for (size_t k = 2, omega_id_delta = n >> 1;
			 k <= n;
			 k <<= 1, omega_id_delta >>= 1) {
			for (size_t i = 0; i < n; i += k) {
				for (size_t j = i, omega_id = 0;
					 (j - i) << 1 < k;
					 j++, omega_id += omega_id_delta) {
					F_o = ANS[j + (k >> 1)] * o[omega_id];
					ANS[j + (k >> 1)] = (ANS[j] - F_o) % big_int_NTT_mod;
					ANS[j] = (ANS[j] + F_o) % big_int_NTT_mod;
				}
			}
		}
	}
	inline void mul(long long *A, long long *B, long long *C) {
		// O(log(mod) + n log(n))
		long long o = quickpower(big_int_NTT_g, (big_int_NTT_mod - 1) >> k);
		long long *ta = new long long[size_t(1) << (k + 1)];
		long long *tb = ta + (size_t(1) << k);
		NTT(A, o, ta);
		NTT(B, o, tb);
		for (size_t i = 0; i < size_t(1) << k; i++) {
			ta[i] *= tb[i];
		}
				// exit(0);
				o = quickpower(o, big_int_NTT_mod - 2);
		NTT(ta, o, C);
		long long inv_n = quickpower(size_t(1) << k, big_int_NTT_mod - 2);
		for (size_t i = 0; i < size_t(1) << k; i++) {
			C[i] = (C[i] * inv_n % big_int_NTT_mod + big_int_NTT_mod) % big_int_NTT_mod;
		}
		delete[] ta;
	}
};
#ifdef __IGNORE__BIG_INT_ERRORS__
#define __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
#endif
template<typename T = int32_t> struct uint_big_t;
template<typename T = int32_t> struct int_big_t;
template<typename T>
struct uint_big_t {
	// unsigned big integer
	// the integer has length digits from 1 to radix^{length-1}
	// output_radix muse less or equal than radix
	// break if visit signs
	// if use operator* with big and big, maybe broken
	// if sizeof(T) is too small, maybe broken
	size_t length;
	unsigned long long radix, output_radix;
	std::vector<T> data;
	uint_big_t()
		: length(0),
		  radix(10),
		  output_radix(10) {}
	uint_big_t(const uint_big_t &d)
		: length(d.length),
		  radix(d.radix),
		  output_radix(d.output_radix),
		  data(d.data) {}
	uint_big_t(uint_big_t &&d)
		: length(d.length),
		  radix(d.radix),
		  output_radix(d.output_radix),
		  data(std::move(d.data)) {}
	// template<typename T2,
			 // typename = std::enable_if_t<std::is_same<uint_big_t<T>, T2>::value> >
	uint_big_t(const std::string &s, unsigned long long input_radix = 10)
		: radix(input_radix),
		  output_radix(input_radix) {
		set_radix(input_radix);
		size_t useful_length = 0;
		for (char i : s) {
			useful_length += bool(~big_int_c2i[radix][size_t(i)]);
		}
		length = useful_length;
		if (useful_length == 0) {
			return;
		}
		data.resize(length = useful_length, 0);
		useful_length = 0;
		for (size_t i = 0; i < s.size(); i++) {
			if (~big_int_c2i[radix][size_t(s[s.size() - i - 1])]) {
				data[useful_length++] = big_int_c2i[radix][size_t(s[s.size() - i - 1])];
			}
		}
		delete_leading_zeros();
	}
	// template<typename T2,
			 // typename = std::enable_if_t<std::is_same<char*, decay<T2> >::value> >
	uint_big_t(const char *s, unsigned long long input_radix = 10)
		: uint_big_t(std::string(s), input_radix) {}
	template<typename T2,
			 typename = std::enable_if_t<std::is_integral<T2>::value> >
	uint_big_t(T2 s, unsigned long long input_radix = 10)
		: radix(input_radix),
		  output_radix(input_radix) {
		if (s < 0) {
			s = -s;
			#ifndef __IGNORE__BIG_INT_ERRORS__
			throw std::runtime_error("Generate unsigned big int from negative number");
			#endif
		}
		while (s) {
			data.push_back(s % T2(input_radix));
			s /= T2(input_radix);
		}
		length = data.size();
	}
	uint_big_t& operator=(const uint_big_t& other) = default;
	uint_big_t& operator=(uint_big_t&& other) = default;
	void delete_leading_zeros() {
		while (!data.empty() && data.back() == 0) data.pop_back();
		length = data.size();
	}
	void carry_bit() {
		// cout << *this << endl;
		if (data.empty()) {
			length = 0;
			return;
		}
		// cout << data << endl;
		// cout << radix << endl;
		for (size_t i = 0; i + 1 < data.size(); i++) {
			// cout << i spc data[i];
			data[i + 1] += data[i] / T(radix);
			data[i] %= T(radix);
			// cout spc data[i] << endl;
			if (data[i] < 0) {
				data[i + 1]--;
				data[i] += T(radix);
			}
		}
		delete_leading_zeros();
		// cout << data << endl;
		while (!data.empty() && data.back() >= T(radix)) {
			// cout << data << endl;
			data.push_back(data.back() / T(radix));
			data.rbegin()[1] %= T(radix);
		}
		length = data.size();
	}
	void shrink(size_t digit_width) {
		// radix -> radix^digit_width
		if (digit_width <= 1) return;
		unsigned long long new_radix = 1;
		for (size_t i = 0; i < digit_width; i++) {
			new_radix *= radix;
		}
		size_t new_length = (length + digit_width - 1) / digit_width;
		while (data.size() % digit_width != 0) {
			data.push_back(0);
		}
		std::vector<T> new_data(new_length, 0);
		for (size_t i = 0; i < new_length; i++) {
			for (size_t j = 0; j < digit_width; j++) {
				new_data[i] = new_data[i] * T(radix) + data[(i + 1) * digit_width - j - 1];
			}
		}
		data = std::move(new_data);
		radix = new_radix;
		length = new_length;
	}
	T &operator[](size_t pos) {
		return data[pos];
	}
	const T &operator[](size_t pos) const {
		return data[pos];
	}
	bool operator<(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length < b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] > b.data[i - 1]) {
				return false;
			} else if (data[i - 1] < b.data[i - 1]) {
				return true;
			}
		}
		return false;
	}
	bool operator>(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length > b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] < b.data[i - 1]) {
				return false;
			} else if (data[i - 1] > b.data[i - 1]) {
				return true;
			}
		}
		return false;
	}
	bool operator==(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length == b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] != b.data[i - 1]) {
				return false;
			}
		}
		return true;
	}
	bool operator!=(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length != b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] != b.data[i - 1]) {
				return true;
			}
		}
		return false;
	}
	bool operator<=(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length < b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] > b.data[i - 1]) {
				return false;
			} else if (data[i - 1] < b.data[i - 1]) {
				return true;
			}
		}
		return true;
	}
	bool operator>=(const uint_big_t &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (length != b.length) {
			return length > b.length;
		}
		for (size_t i = length; i > 0; i--) {
			if (data[i - 1] < b.data[i - 1]) {
				return false;
			} else if (data[i - 1] > b.data[i - 1]) {
				return true;
			}
		}
		return true;
	}
	template<typename T2>
	std::enable_if_t<std::is_same<uint_big_t, std::decay_t<T2> >::value, uint_big_t&>
	operator+=(const T2 &b) {
		// ubig += ubig
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (b.data.size() > data.size()) {
			data.resize(b.data.size());
		}
		for (size_t i = 0; i < b.data.size(); i++) {
			data[i] += b.data[i];
		}
		carry_bit();
		return *this;
	}
	template<typename T2>
	std::enable_if_t<std::is_same<uint_big_t, std::decay_t<T2> >::value, uint_big_t>
	operator+(const T2 &b) const {
		// ubig + ubig
		uint_big_t ans = *this;
		return ans += b;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t&>
	operator+=(T2 b_) {
		long long b = b_;
		// ubig += small
		for (size_t i = 0; i < length; i++) {
			b += data[i];
			data[i] = b % T2(radix);
			b /= T2(radix);
			// cout << i spc b spc data << endl;
			if (b == 0) {
				delete_leading_zeros();
				return *this;
			}
		}
		while (b) {
			data.push_back(b % T2(radix));
			b /= T2(radix);
		}
		delete_leading_zeros();
		return *this;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t>
	operator+(T2 b) const {
		// ubig + small
		uint_big_t ans = *this;
		return ans += b;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t&>
	operator/=(T2 b_) {
		// ubig /= small
		unsigned long long b = b_;
		unsigned long long res = 0;
		for (size_t i = length; i > 0; i--) {
			res = res * radix + data[i - 1];
			data[i - 1] = T2(res) / b;
			res %= b;
			// cout << i spc res spc data << endl;
		}
		delete_leading_zeros();
		return *this;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t>
	operator/(T2 b) const {
		// ubig / small
		if (b <= 0) return {};
		else if (b == 1) return *this;
		uint_big_t ans = *this;
		return ans /= b;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, T2>
	operator%(T2 b_) const {
		// ubig % small
		// cout << data << " % " << b_ << endl;
		unsigned long long b = b_;
		unsigned long long res = 0;
		for (size_t i = length; i > 0; i--) {
			res = res * radix + data[i - 1];
			res %= b;
			// cout << i spc res spc data << endl;
		}
		// cout << " = " <<
		return res;
	}
	uint_big_t &operator-=(const uint_big_t &b) {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		// cout << *this << " -= " << b << endl;
		if (b.data.size() > data.size()) {
			data.resize(b.data.size());
		}
		// cout << data << " " << b.data << endl;
		for (size_t i = 0; i < b.data.size(); i++) {
			data[i] -= b.data[i];
		}
		carry_bit();
		return *this;
	}
	uint_big_t operator-(const uint_big_t &b) const {
		uint_big_t ans = *this;
		// cout << ans << " - " << b << endl;
		return ans -= b;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t&>
	operator*=(T2 b_) {
		// ubig *= small
		// cout << data << " *= " << b_ << endl;
		unsigned long long b = b_;
		unsigned long long res = 0;
		for (size_t i = 0; i < length; i++) {
			res += data[i] * b;
			// cout << i spc res spc data << endl;
			data[i] = res % radix;
			res /= radix;
		}
		while (res) {
			data.push_back(res % radix);
			res /= radix;
		}
		delete_leading_zeros();
		// cout << data << endl;
		return *this;
	}
	template<typename T2>
	std::enable_if_t<std::is_integral<std::decay_t<T2> >::value, uint_big_t>
	operator*(T2 b) const {
		// ubig * small
		if (b <= 0) return {};
		else if (b == 1) return *this;
		uint_big_t ans = *this;
		return ans /= b;
	}
	template<typename T2>
	std::enable_if_t<std::is_same<uint_big_t, std::decay_t<T2> >::value, uint_big_t>
	operator*(const T2 &b) const {
		#ifndef __IGNORE__DIFFERENT_RADIX_BIG_INT_OPERATION_ERROR__
		if (radix != b.radix) {
			throw std::runtime_error("The radix of big int is different.");
		}
		#endif
		if (b.length == 0) return b;
		if (length == 0) return *this;
		// if (length >= 16 || b.length >= 16) {
		// cout << data << endl << b.data << endl;
			size_t k = 0;
			while (size_t(1) << k < length + b.length - 1) k++;
			long long *A = new long long[size_t(3) << k];
			long long *B = A + (size_t(1) << k);
			long long *C = B + (size_t(1) << k);
			memset(A, 0, (sizeof(long long) * 3) << k);
			for (size_t i = 0; i < length; i++) {
				A[i] = data[i];
			}
			for (size_t i = 0; i < b.length; i++) {
				B[i] = b.data[i];
			}
			// cout << std::vector<int>(A, A + (size_t(1) << k)) << endl;
			// cout << std::vector<int>(B, B + (size_t(1) << k)) << endl;
			NTT_calculator(k).mul(A, B, C);
			// cout << std::vector<int>(C, C + (size_t(1) << k)) << endl;
			uint_big_t ans;
			ans.radix = radix;
			ans.output_radix = output_radix;
			unsigned long long res = 0;
			for (size_t i = 0; i < (size_t(1) << k); i++) {
				ans.data.push_back((res += C[i]) % radix);
				res /= radix;
			}
			while (res) {
				ans.data.push_back(res % radix);
				res /= radix;
			}
			ans.delete_leading_zeros();
			delete[] A;
		// cout << data << endl << endl;
			return ans;
		// }
	}
	template<typename T2>
	std::enable_if_t<std::is_same<uint_big_t, std::decay_t<T2> >::value, uint_big_t&>
	&operator*=(const T2 &b) {
		return *this = *this * b;
	}
	const uint_big_t &operator+() const {
		return *this;
	}
	int_big_t<T> operator-() const;
	int_big_t<T> to_signed() const;
	template<typename T2,
			 typename = std::enable_if_t<std::is_integral<T2>::value
			 					 || std::is_floating_point<T2>::value> >
	operator T2() const {
		std::decay_t<T2> ans = 0;
		for (size_t i = length; i > 0; i--) {
			ans = ans * static_cast<std::decay_t<T2> >(radix) + data[i-1];
		}
		return ans;
	}
	template<typename T2>
	friend std::ostream &operator<<(std::ostream &a, const uint_big_t<T2> &b);
	template<typename T2>
	friend std::istream &operator>>(std::istream &a, uint_big_t<T2> &b);
};
template<typename T>
std::ostream &operator<<(std::ostream &a, const uint_big_t<T> &b) {
	set_radix(b.output_radix);
	size_t digit_width = 1;
	unsigned long long digit_size = b.output_radix;
	while (digit_size < b.radix) {
		digit_width++;
		digit_size *= b.output_radix;
	}
	if (b.length == 0) {
		return a << 0;
	}
	std::vector<char> out;
	for (size_t i = 0; i < b.length; i++) {
		if (i + 1 != b.length) {
			T now = b[i];
			for (size_t j = 0; j < digit_width; j++) {
				out.push_back(big_int_i2c(now % b.output_radix));
				now /= b.output_radix;
			}
		} else {
			T now = b[i];
			while (now) {
				out.push_back(big_int_i2c(now % b.output_radix));
				now /= b.output_radix;
			}
		}
	}
	return a << std::string(out.rbegin(), out.rend());
}
template<typename T>
std::istream &operator>>(std::istream &a, uint_big_t<T> &b) {
	// b.radix = b.output_radix = default_radix;
	set_radix(b.radix);
	static char c;
	do {
		c = a.get();
	} while (!~big_int_c2i[b.radix][size_t((unsigned char)(c))]);
	do {
		b.data.push_back(big_int_c2i[b.radix][size_t((unsigned char)(c))]);
		c = a.get();
	} while (~big_int_c2i[b.radix][size_t((unsigned char)(c))]);
	reverse(b.data.begin(), b.data.end());
	b.delete_leading_zeros();
	a.unget();
	return a;
}
template<typename T>
struct int_big_t {
	uint_big_t<T> data;
	bool sign;
	int_big_t() : sign(false) {}
	int_big_t(const uint_big_t<T> &d, bool s = false) : data(d), sign(s) {}
	int_big_t(uint_big_t<T> &&d, bool s = false) : data(std::move(d)), sign(s) {}
	int_big_t(const std::string &s, unsigned long long input_radix) : sign(false) {
		set_radix(data.radix);
		for (size_t i = 0; i < s.size(); i++) {
			if (s[i] == '-') {
				data = uint_big_t<T>(s.substr(i + 1), input_radix);
				sign = true;
				break;
			} else if (s[i] == '+') {
				data = uint_big_t<T>(s.substr(i + 1), input_radix);
				break;
			} else if (big_int_c2i[data.radix][size_t(s[i])]) {
				data = uint_big_t<T>(s.substr(i), input_radix);
				break;
			}
		}
	}
	int_big_t(const char *s, unsigned long long input_radix)
		: int_big_t(std::string(s), input_radix) {}
	template<typename T2,
			 typename = std::enable_if_t<std::is_integral<T2>::value> >
	int_big_t(T2 a, unsigned long long input_radix = 10) : sign(false) {
		if (a < 0) {
			sign = true;
			a = -a;
		}
		data = uint_big_t<T>(a, input_radix);
	}
	int_big_t(const int_big_t &other) = default;
	int_big_t(int_big_t &&other) = default;
	int_big_t& operator=(const int_big_t& other) = default;
	int_big_t& operator=(int_big_t&& other) = default;
	void shrink(size_t digit_width) { data.shrink(digit_width); }
	template<typename T2>
	std::enable_if_t<std::is_same<int_big_t<T>, std::decay_t<T2> >::value, int_big_t&>
	operator+=(const T2 &b) {
		if (sign && b.sign) {
			data += b.data;
			return *this;
		} else if (!sign && !b.sign) {
			data += b.data;
			return *this;
		}
		if (sign && !b.sign) {
			if (b.data >= data) {
				data = b.data - data;
				sign = false;
				return *this;
			} else {
				data -= b.data;
				return *this;
			}
		} else {
			if (b.data > data) {
				data = b.data - data;
				sign = true;
				return *this;
			} else {
				data -= b.data;
				return *this;
			}
		}
	}
	template<typename T2>
	std::enable_if_t<std::is_same<int_big_t<T>, std::decay_t<T2> >::value, int_big_t>
	operator+(const T2 &b) const {
		int_big_t ans = *this;
		return ans += b;
	}
	int_big_t &operator-=(const int_big_t &b) {
		if (sign && !b.sign) {
			data += b.data;
			return *this;
		} else if (!sign && b.sign) {
			data += b.data;
			return *this;
		}
		if (sign && b.sign) {
			if (b.data >= data) {
				data = b.data - data;
				sign = false;
				return *this;
			} else {
				data -= b.data;
				return *this;
			}
		} else {
			if (b.data > data) {
				data = b.data - data;
				sign = true;
				return *this;
			} else {
				data -= b.data;
				return *this;
			}
		}
	}
	int_big_t operator-(const int_big_t &b) const {
		int_big_t ans = *this;
		return ans -= b;
	}
	int_big_t operator*(const int_big_t &b) const {
		return {data * b.data, bool(int(sign) ^ int(b.sign))};
	}
	int_big_t &operator*=(const int_big_t &b) {
		return *this = *this * b;
	}
	T &operator[](size_t pos) {
		return data.data[pos];
	}
	const T &operator[](size_t pos) const {
		return data.data[pos];
	}
	int_big_t operator-() const {
		return {data, !sign};
	}
	const int_big_t &operator+() const {
		return *this;
	}
	template<typename T2,
			 typename = std::enable_if_t<std::is_integral<T2>::value
			 					 || std::is_floating_point<T2>::value> >
	operator T2() const {
		return sign ? -T2(data) : T2(data);
	}
	template<typename T2>
	friend std::ostream &operator<<(std::ostream &a, const int_big_t<T2> &b);
	template<typename T2>
	friend std::istream &operator>>(std::istream &a, int_big_t<T2> &b);
};
template<typename T>
std::ostream &operator<<(std::ostream &a, const int_big_t<T> &b) {
	if (b.sign) a << '-';
	return a << b.data;
}
template<typename T>
std::istream &operator>>(std::istream &a, int_big_t<T> &b) {
	// b.data.radix = b.data.output_radix = default_radix;
	set_radix(b.data.radix);
	static char c;
	do {
		c = a.get();
	} while (c != '-' && c != '+' && !~big_int_c2i[b.data.radix][size_t((unsigned char)(c))]);
	b.sign = false;
	if (c == '-') {
		b.sign = true;
		c = a.get();
	} else if (c == '+') {
		c = a.get();
	}
	do {
		b.data.data.push_back(big_int_c2i[b.data.radix][size_t((unsigned char)(c))]);
		// cout << big_int_c2i[size_t((unsigned char)(c))] << endl;
		c = a.get();
	} while (~big_int_c2i[b.data.radix][size_t((unsigned char)(c))]);
	reverse(b.data.data.begin(), b.data.data.end());
	b.data.delete_leading_zeros();
	a.unget();
	return a;
}
template<typename T>
int_big_t<T> uint_big_t<T>::operator-() const {
	return {*this, true};
}
template<typename T>
int_big_t<T> uint_big_t<T>::to_signed() const {
	return {*this, false};
}
using namespace std;
signed main() {
	int_big_t<> a, b;
	cin >> a >> b;
	a.shrink(3);
	b.shrink(3);
	cout << a * b << endl;
	return 0;
}

评测结果