另外两篇题解的大佬都用 FFT 或者 python，好羡慕他们会 FFT 啊（雾）~

窝太菜了，只是刚学 FNTT，勉强过去就算了吧（雾）

给个 code：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int P = 1004535809, NN = 1e5 + 5;

int n, N, M;
int A[1 << 18], B[1 << 18], h[1 << 18], sum[NN], ww[1 << 19], *e = ww + (1 << 18);
int res[NN];

int qmi (int base, int exp) {

    int res = 1;

    for (; exp; exp >>= 1, base = base * base % P)
        if (exp & 1)    res = res * base % P;

    return res;
}

char s1[NN], s2[NN];

void FNTT (int *x, int n, int c) {

    int *a = x, *b = h, l, r;

    for (int i = n; i > 1; i >>= 1, swap (a, b))
        for (int j = 0; j < n; j += i)
            for (int k = 0; k < i; k += 2)

                b[j + (k >> 1)] = a[j + k],
                b[j + (k >> 1) + (i >> 1)] = a[j + k + 1];

    for (int i = 2; i <= n; i <<= 1, swap (a, b))
        for (int w = 0, k = 0; k < (i >> 1); k ++, w += n / i * c)
            for (int j = 0; j < n; j += i) {

                l = a[j + k],
                r = e[w] * a[j + (i >> 1) + k] % P;
                b[j + k] = ((l + r >= P) ? l + r - P : l + r);
                b[j + (i >> 1) + k] = ((l - r < 0) ? l - r + P : l - r);
            }

    for (int i = 0; i < n; i ++)
        x[i] = a[i];

    return;
}

signed main() {

    scanf ("%s%s", s1, s2);

    N = strlen (s1); M = strlen (s2);

    for (int i = 0; i < N; i ++)
        A[N - i - 1] = s1[i] - '0';

    for (int i = 0; i < M; i ++)
        B[M - i - 1] = s2[i] - '0';

    for (n = 1; n < N + M; n <<= 1);

    e[0] = e[-n] = 1;
    e[1] = e[1 - n] = qmi (3, (P - 1) / n);

    for (int i = 2; i < n; i ++)
        e[i - n] = e[i] = e[i - 1] * e[1] % P;

    FNTT (A, n, 1);
    FNTT (B, n, 1);

    for (int i = 0; i < n; i ++)
        A[i] = A[i] * B[i] % P;

    FNTT (A, n, -1);

    int ny = qmi (n, P - 2);

    for (int i = 0; i < n; i ++)
        A[i] = A[i] * ny % P;

    for (int i = 0; i < n - 1; i ++)

        A[i + 1] += A[i] / 10,
        A[i] %= 10;

    int i = n - 1;
    while (!A[i]) -- i;

    for (; ~i; i --)
        putchar ('0' + A[i]);

    return 0;
}