#include <cstdio> // For scanf, printf, strlen
#include <string> // For std::string, std::to_string
#include <vector> // For std::vector
#include <algorithm> // For std::reverse, std::swap, std::max
#include <iostream> // For std::ios_base, std::cin, std::tie
// 常量用於NTT: MOD為質數,G為原根。
// 998244353是常見的NTT模數,因為它是一個質數,且 (MOD - 1) 包含足夠大的 2 的冪因子 (2^23)。
const int MOD = 998244353;
const int G = 3; // 3 是 998244353 的一個原根。
// 模冪運算 (a^b % MOD)
int fastpow(int a, int b) {
int res = 1;
a %= MOD;
while (b) {
if (b & 1) res = (int)((long long)res * a % MOD);
a = (int)((long long)a * a % MOD);
b >>= 1;
}
return res;
}
// 數論變換 (NTT)
// a: 係數向量
// invert: true 為逆變換 (IDFT/INTT),false 為正變換 (DFT/NTT)
void ntt(std::vector<int> &a, bool invert) {
int n = (int)a.size();
// 重新排序位數 (bit-reversal permutation)
// 使得之後的蝴蝶操作能在正確位置上執行
for (int i = 1, j = 0; i < n; ++i) {
int bit = n >> 1;
// Fix: Should be bit >>= 1, not bit >>= 0
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j) std::swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
// 計算原根 wlen,對於正變換使用 G,對於逆變換使用 G 的模逆元
int wlen = fastpow(G, (MOD - 1) / len);
if (invert) wlen = fastpow(wlen, MOD - 2); // wlen的模逆元 (費馬小定理: a^(MOD-2) = a^-1 mod MOD)
for (int i = 0; i < n; i += len) {
int w = 1; // 每一段的乘數
int half = len >> 1; // 半段長度
for (int j = 0; j < half; ++j) {
int u = a[i + j]; // 上半部分的結果
int v = (int)((long long)a[i + j + half] * w % MOD); // 下半部分乘上 w
a[i + j] = u + v; // 相加
if (a[i + j] >= MOD) a[i + j] -= MOD;
a[i + j + half] = u - v; // 相減
if (a[i + j + half] < 0) a[i + j + half] += MOD;
w = (int)((long long)w * wlen % MOD); // 更新 w
}
}
}
// 逆變換結束後,需要將結果除以 n (乘上 n 的模逆元)
if (invert) {
int inv_n = fastpow(n, MOD - 2); // n的模逆元
for (int &x : a)
x = (int)((long long)x * inv_n % MOD);
}
}
// 將數字字串解析成數字向量 (reverse order: 低位在前)
std::vector<int> parse(const std::string &s) {
std::vector<int> v(s.length());
for (int i = 0; i < (int)s.length(); ++i) {
v[i] = s[s.length() - 1 - i] - '0'; // 低位到高位
}
return v;
}
// 從數字向量轉換回字串 (同時去除前導零)
std::string vectorToString(const std::vector<int> &v) {
if (v.empty()) return "0"; // Handle empty vector
int i = (int)v.size() - 1;
while (i > 0 && v[i] == 0) i--; // 跳過高位多餘的0 (從右邊往左邊)
std::string s = "";
s.reserve(i + 1); // Pre-allocate string for efficiency
for (; i >= 0; i--) {
s += (v[i] + '0');
}
return s.empty() ? "0" : s; // 如果字符串仍然为空(如输入是"0"),則返回"0"
}
// 加法運算
std::vector<int> add(const std::vector<int> &a, const std::vector<int> &b) {
int n = (int)std::max(a.size(), b.size());
std::vector<int> res;
res.reserve(n + 1); // 預留空間,最多比大數多一位
int carry = 0;
for (int i = 0; i < n || carry; ++i) {
int x = carry;
if (i < (int)a.size()) x += a[i];
if (i < (int)b.size()) x += b[i];
res.push_back(x % 10);
carry = x / 10;
}
return res; // 低位在前,vectorToString 會處理顯示
}
// 比較兩個數的大小 (字串形式),sa < sb 返回 true
bool isSmaller(const std::string& sa, const std::string& sb) {
if (sa.length() != sb.length()) {
return sa.length() < sb.length();
}
return sa < sb; // 相同長度時直接比較字串 (字典序)
}
// 減法運算 (確保第一個參數的數值大於或等於第二個參數)
std::vector<int> subtract_non_negative(const std::vector<int> &a, const std::vector<int> &b) {
std::vector<int> res;
res.reserve(a.size()); // 預留空間
int borrow = 0;
for (int i = 0; i < (int)a.size(); ++i) {
int x = a[i] - borrow - (i < (int)b.size() ? b[i] : 0);
if (x < 0) {
x += 10;
borrow = 1;
} else {
borrow = 0;
}
res.push_back(x);
}
// 返回結果時,會保留所有的0,vectorToString會處理顯示前導零。
return res;
}
// 乘法運算
std::vector<int> multiply(std::vector<int> a, std::vector<int> b) {
// 找出 NTT 運算所需的最小 2 的冪次大小 n
// n 必須大於等於 (a的位數 + b的位數 - 1),因為結果多項式 degree is deg(A) + deg(B)
int n = 1;
// (a.size() + b.size() - 1) 代表結果多項式的最大項數
while (n < (int)(a.size() + b.size() - 1))
n <<= 1;
a.resize(n, 0); // 擴展到 n 位並補0
b.resize(n, 0); // 擴展到 n 位並補0
// 對 a 和 b 執行 NTT
ntt(a, false);
ntt(b, false);
// 在頻域 (DFT) 進行點乘
for (int i = 0; i < n; i++)
a[i] = (int)((long long)a[i] * b[i] % MOD);
// 對結果執行逆 NTT,將頻域轉回時域
ntt(a, true);
std::vector<int> res;
// 結果的長度最多為輸入長度之和 + 1 (考慮進位)
res.reserve(a.size() + b.size() + 2); // 稍微多一些的預留空間
long long carry = 0; // 進位
// 循環處理所有可能的結果位元和進位
for (int i = 0; i < n || carry; i++) {
long long current_val = (i < n ? a[i] : 0) + carry; // 當前位的值加上進位 (如果超過n則取0)
res.push_back(int(current_val % 10)); // 當前位的實際數字
carry = current_val / 10; // 計算新的進位
}
return res; // 返回的vector是低位在前,vectorToString會處理顯示
}
char A_str_input[1000002]; // 輸入 A 的字元陣列
char B_str_input[1000002]; // 輸入 B 的字元陣列
int main() {
// 加速 C++ 標準 I/O,這對於大型輸入很重要
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
char op_char;
// 使用 scanf 讀取以保持與您原先程式碼輸入方式一致,並避免-Wunused-result警告
(void)scanf("%s %c %s", A_str_input, &op_char, B_str_input);
std::string A_str(A_str_input);
std::string B_str(B_str_input);
std::string op_str(1, op_char); // 將 char 轉為 string 便於比較
std::vector<int> a_parsed = parse(A_str);
std::vector<int> b_parsed = parse(B_str);
std::vector<int> result_vec;
if (op_str == "+") {
result_vec = add(a_parsed, b_parsed);
} else if (op_str == "-") {
// 特殊處理 "0 - 0"
if (A_str == "0" && B_str == "0") {
printf("0\n");
return 0;
}
if (A_str == B_str) {
printf("0\n"); // 如果 A == B,直接輸出 0
return 0;
} else if (isSmaller(A_str, B_str)) {
// 如果 A < B,結果為負數,先計算 B - A,然後加負號
result_vec = subtract_non_negative(b_parsed, a_parsed);
printf("-%s\n", vectorToString(result_vec).c_str());
return 0; // 輸出完畢,程式結束
} else {
// 如果 A > B,直接計算 A - B
result_vec = subtract_non_negative(a_parsed, b_parsed);
}
} else if (op_str == "*") {
// 特殊處理乘以 0 的情況,避免不必要的NTT運算
if (A_str == "0" || B_str == "0") {
printf("0\n");
return 0;
}
result_vec = multiply(a_parsed, b_parsed);
}
// 打印最終結果
printf("%s\n", vectorToString(result_vec).c_str());
return 0;