Big Number Multiplication (2)

Time limit2sMemory limit512 MB

Summary

Multiply two integers of up to 300,000 digits each, too large for quadratic multiplication, and print the exact product.

Level: Hard8 of 10
Topics: Math, Divide and conquer, String, Implementation
Solved: No attempts yet

Problem

You are given two integers A and B. Write a program that prints their product.

Each number has up to 300,000 digits, so a multiplication that costs time proportional to the square of the digit count cannot finish within the time limit.

Input

The first line contains the integers A and B, separated by a single space. Both numbers are at least 0, and apart from the number 0 itself no number starts with the digit 0, so there are no unnecessary leading zeros. A and B each have at most 300,000 digits.

Output

Print the product of A and B on the first line. Do not print unnecessary leading zeros, and if the product is 0, print a single 0.

Examples3

Example 1
Input
```
1 2
```
Expected output
```
2
```
Example 2
Input
```
3 4
```
Expected output
```
12
```

Example 3

Input

893724358493284 238947328947329

Expected output

213553048277135320552236238436