For a given positive integer n denote its k-rounding as the minimum positive integer x, such that x ends with k or more zeros in base 10 and is divisible by n.

For example, 4-rounding of 375 is 375·80 = 30000. 30000 is the minimum integer such that it ends with 4 or more zeros and is divisible by 375.

Write a program that will perform the k-rounding of n.

Input

The only line contains two integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 8).

Output

Print the k-rounding of n.

Examples

Input

375 4

Output

30000

Input

10000 1

Output

10000

Input

38101 0

Output

38101

Input

123456789 8

Output

12345678900000000

 

题意，找一个最小的x，使满足n*x%(10^k)==0,即n*x==(10^k)*y,也即n*x===0(mod (10^k))

可以用ex_gcd来解方程，过程是：先求出n*x+（10^k）*y==gcd（n，10^k）的解，再乘0/gcd就是方程的一个特解（其实不用ex_gcd，因为特解一定是（0，0））。然后求大于0的最小x，即0+1*（10^k）/gcd(n,10^k),n*x=lcm(n,10^k)

 

 

或者利用唯一分解定理，把n和10^k分解为若干素数的乘积，可以想象，要使n*x模10^k等于0，那么n*x就是lcm(n,10^k)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,k;

ll fac(ll x)
{
	ll ret=1;
	while(x--)ret*=10;
	return ret;
}

int main()
{
	cin>>n>>k;
	cout<<fac(k)/__gcd(n,fac(k))*n<<endl;
	return 0;
}