Nastya received a gift on New Year — a magic wardrobe. It is magic because in the end of each month the number of dresses in it doubles (i.e. the number of dresses becomes twice as large as it is in the beginning of the month).

Unfortunately, right after the doubling the wardrobe eats one of the dresses (if any) with the 50% probability. It happens every month except the last one in the year. 

Nastya owns x dresses now, so she became interested in the expected number of dresses she will have in one year. Nastya lives in Byteland, so the year lasts for k + 1 months.

Nastya is really busy, so she wants you to solve this problem. You are the programmer, after all. Also, you should find the answer modulo 10^9 + 7, because it is easy to see that it is always integer.


-----Input-----

The only line contains two integers x and k (0 ≤ x, k ≤ 10^18), where x is the initial number of dresses and k + 1 is the number of months in a year in Byteland.


-----Output-----

In the only line print a single integer — the expected number of dresses Nastya will own one year later modulo 10^9 + 7.


-----Examples-----
Input
2 0

Output
4

Input
2 1

Output
7

Input
3 2

Output
21



-----Note-----

In the first example a year consists on only one month, so the wardrobe does not eat dresses at all.

In the second example after the first month there are 3 dresses with 50% probability and 4 dresses with 50% probability. Thus, in the end of the year there are 6 dresses with 50% probability and 8 dresses with 50% probability. This way the answer for this test is (6 + 8) / 2 = 7.

Difficulty: interview

Starter code:

Solutions:
x, k = map(int, input().split())
if x == 0:
    print(0)
else:
    mod = 10 ** 9 + 7
    p = pow(2, k, mod)
    ans = (x * (p * 2) - (p - 1)) % mod
    print(ans)

mod = 10**9+7
x, k = list(map(int, input().split(' ')))
if (x == 0):
    print(0)
else:
    val1 = pow(2,k+1,mod) * x
    val2 = pow(2, k, mod) - 1
    val1 -= val2
    val1 %= mod
    print(val1)




x,k = map(int, input().strip().split())

MOD = 1000000007

if x > 0:
	r = (pow(2, k+1, MOD) * x - pow(2, k, MOD) + 1 + MOD * 10) % MOD
else:
	r = 0

print(r)

from sys import stdin

line = stdin.readline().rstrip().split()
x = int(line[0])
k = int(line[1])

if x == 0:
    print(0)
else:
    nn = pow(2, k, 1000000007)
    result = (nn*2*x - nn + 1) % 1000000007
    print(result)





l = input().split(' ')
x = int(l[0])
k = int(l[1])

if x == 0:
    print('0')
else:
    mod = 1000000007

    def pow_mod(a, b):
        if b < 2:
            return int(a ** b) % mod
        elif b % 2 == 0:
            return int(pow_mod(a, b // 2) ** 2) % mod
        else:
            return pow_mod(a, b - 1) * a % mod

    twop = pow_mod(2, k)
    high = x * twop
    leafs = twop
    low = high - leafs + 1
    s = (high + 1) * high // 2 - (low - 1 + 1) * (low - 1) // 2
    answer = s * 2 // leafs
    answer %= mod

    print(answer)

x, k = map(int, input().split())
ans = 0
md = 1000000007

def bpow(base, exp, md):
    if (exp == 0):
        return 1
    if (exp % 2 == 1):
        return (base * bpow(base, exp-1, md)) % md
    else:
        k = bpow(base, exp//2, md)
        return (k*k) % md

pw = bpow(2, k, md)
ans = (2 * pw * x) % md
if (x != 0):
    ans -= pw-1
ans = (ans + md) % md
print(ans)

x, k = list(map(int, input().split()))
if x == 0:
    print(0)
    return
x = 2 * x - 1
mod = 10**9 + 7

def pot(r, k):
    if k == 0: return 1
    if k % 2 == 1:
        return r * pot(r, k - 1) % mod
    y = pot(r, k // 2)
    return y * y % mod

print((pot(2, k) * x + 1) % mod)


mod = 1000000007
x, k = map(int, input().split())
if x == 0:
    print(0)
else:
    ans = (pow(2, k + 1, mod) * x % mod - (pow(2, k, mod) - 1 + mod) % mod + mod) % mod
    print(ans)

x, k = map(int, input().split())
if x == 0:
    print(0)
    return
res = pow(2, k + 1, 10 ** 9 + 7) * x - pow(2, k, 10 ** 9 + 7) + 1
res %= 10 ** 9 + 7
print(res)

x, k = map(int, input().split())
mod = 1000000007
flag = True
if x==0:
	flag = False

x = x%mod
y = pow(2, k+1, mod)
z = pow(2, k, mod) - 1

x = x*y
x = x%mod
x = x-z
if x==0:
	x=x+mod
x = x%mod

if flag:
	print(x)
else:
	print(0)

from sys import stdin, stdout


MOD = 10 ** 9 + 7


def bin_pow(n, k):
    res = 1
    
    while k:
        if k & 1:
            res = (res * n) % MOD
        
        n = (n * n) % MOD
        k >>= 1
        
    return res


x, k = map(int, stdin.readline().split())

if x == 0:
    stdout.write('0')
else:
    ans = (bin_pow(2, k + 1) * x - bin_pow(2, k) + 1) % MOD
    stdout.write(str(ans))

x,k = list(map(int, input().split()))
mod = 10 ** 9 + 7
print(0 if x == 0 else (x * pow(2, k + 1, mod) - pow(2, k, mod) + 1 + mod) % mod)


x, k = list(map(int, input().split()))
mod = 1000000007
if (k == 0):
    print((2 * x) % mod)
elif (x == 0):
    print(0)
else:
    ans = ((2 * x - 1) * pow(2, k, mod) + 1) % mod
    print(ans)


x, k = map(int, input().split())

mod = 10**9+7

def bp(n,p):
  if p == 0:
    return 1
  elif p % 2 == 0:
    return bp(n**2 % mod, p // 2)
  else:
    return (bp(n**2 % mod, p // 2) * n) % mod

def f(n,x):
  return (bp(2,n) * x - bp(2,n) + 1) % mod

if x > 0:
  print(f(k,2*x) % mod)
else:
  print(0)

def pwr(a,n,m):
    if n==0:return 1
    ans=pwr(a,n//2,m)
    ans=ans*ans
    ans%=m
    if n%2==1:return (ans*a)%m
    else: return ans
M=1000000007
tx,tn=input().split()
x=int(tx)
n=int(tn)
ans=pwr(2,n+1,M)*x
ans%=M
ans=ans-pwr(2,n,M)+1
ans=(ans+M)%M
if x==0: ans=0
print(ans)


#     Codeforces Round #489 (Div. 2)
import collections
from functools import cmp_to_key
#key=cmp_to_key(lambda x,y: 1 if x not in y else -1 )

import sys
def getIntList():
    return list(map(int, input().split()))    

import bisect 
            
base = 10**9  + 7    
def get2k(k) :
    f = 2
    b = 1
    r = 1
    while k>=b:
        if k &b >0:
            r = r*f % base
        b*=2
        f = f*f % base
    return r

x, k = getIntList()
if x ==0:
    print(0)
    return
t2k = get2k(k)

r = x *   t2k *2 - t2k + 1
r = r% base
print(r)



x, k = [int(x) for x in input().split()]

if x == 0:
    print(0)
    return

mod = 10 ** 9 + 7

res = x * pow(2, k + 1, mod) % mod
res = ((res - (pow(2, k, mod) - 1)) % mod + mod) % mod

print(res)


def my_pow(a, n, m):
	if (n == 0) : return 1
	ans = my_pow(a, n // 2, m)
	if (n % 2 == 0):
		return ans * ans % m
	else:
		return (ans * ans * a) % m

x, k = map(int, input().split())
if (x == 0):
	print(0)
else:
	mod = 10**9 + 7
	x *= 2
	ans = (x - 1) * my_pow(2, k, mod) + 1
	ans %= mod
	ans += 2 * mod
	print(ans % mod)

def binPow(x, n, r):
	if n == 0:
		return 1
	elif n == 1:
		return x % r
	if n % 2 == 0:
		return binPow((x * x) % r, n // 2, r)
	return (binPow((x * x) % r, n // 2, r) * x) % r

x, k = list(map(int, input().split()))
r = 10 ** 9 + 7
if x == 0:
	print(0)
	return
elif k == 0:
	print((x * 2) % r)
	return
print((binPow(2, k, r) * (2 * x - 1) + 1) % r)


MOD = 1000*1000*1000+7

def pow(x,e,m):
    res = 1
    x = x % m

    while e>0:
        if(e % 2 == 1):
            res = (res*x) % m

        e = e//2
        x = (x*x) % m

    return res

x, k = map(int, input().split(' '))


if x == 0:
    print(0)

else:
    myres = (pow(2,k,MOD)*(2*x-1) + 1) % MOD
    print(myres)

x,k = list(map(int,input().split()))
mod = 10**9 + 7
if x == 0:
    print(0)
else:
    print(((2*x-1)*pow(2,k,mod) + 1)%mod)


def powermod(base, power):
    if power == 0: return 1
    if power == 1: return base
    ret = powermod(base, power // 2)
    ret *= ret
    ret %= 1000000007
    if power % 2 == 1:
        ret *= base
        ret %= 1000000007
    return ret

x, k = list(map(int, input().split()))

b = x * 2 - 1
ans = b * powermod(2, k) + 1
ans %= 1000000007

if x == 0: ans = 0
print (ans)


#!/usr/bin/env python3


mod = 10**9 + 7


[x, k] = list(map(int, input().strip().split()))

if x == 0:
	print(0)
	return


def pow2(n):
	if n == 0:
		return 1
	if n % 2 == 0:
		return (pow2(n // 2) ** 2) % mod
	else:
		return (((pow2(n // 2) ** 2) % mod) * 2) % mod

print((pow2(k) * ((2 * x - 1) % mod) + 1) % mod)


mod=1000000007
def fastexp(base,exp):
    if(exp==0):
        return 1;
    if(exp==1):
        return base%mod;
    t=fastexp(base,exp//2);
    if(exp%2==0):
        return (t%mod*t%mod)%mod;
    else:
        return (t%mod*t%mod*base%mod)%mod;
x,k=list(map(int,input().split()))
if(x==0):
    print((0));
else:
    t=fastexp(2,k)%mod;
    before=((2*t)%mod*x%mod)%mod-(t+mod-1)%mod
    while(before<0):
        before+=mod;
    before=before%mod;
    print(before)


x, k = [int(v) for v in input().split()]
mod = 10**9 + 7

if x == 0:
    print(0)
else:
    print(((pow(2, k + 1, mod) * x) - (pow(2, k, mod) - 1)) % mod)