Time Limit: 2s Memory Limit: 256MB

题目描述

为了欺负不会写高精度也不会写 FFT 的 lglg,tyl 考了他这么一个问题:给定两个不超过 2000000 位的超大整数,求这两个整数的乘积,答案对 1e9+7 取模。
lglg 稍加思考,识破,现在他把这个问题交给了你。

输入格式

第一行是一个正整数 \(T\;(1 <= T <= 200)\),表示数据组数。
每一组测试用例包含两行,每行是一个由数字构成的长度不超过 2000000 位的字符串,表示一个大整数。

数据保证所有数字的长度总和不超过 10000000。

输出格式

对于每组测试用例,输出一行,包含一个数,表示两个大整数的乘积,答案对 1e9+7 取模。

样例输入

2
5
6
7
8

样例输出

30
56