【模板】A*B Problem升级版(FFT快速傅里叶)

题目背景

本题数据已加强,请使用 FFT/NTT,不要再交 Python 代码浪费评测资源。

题目描述

给你两个正整数 $a,b$,求 $a \times b$。

输入输出格式

输入格式


第一行一个正整数,表示 $a$; 第二行一个正整数,表示 $b$。

输出格式


输出一行一个整数表示答案。

输入输出样例

输入样例 #1

114514 
1919810

输出样例 #1

219845122340

说明

【数据范围】 $1\le a,b \le 10^{1000000}$ 可能需要一定程度的常数优化。 数据由 NaCly_Fish 重造