写一下二叉树 推一下公式就出来了， 注意取模时的输出形式
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int maxn = 1e6+, INF = 0x7fffffff, MOD = 1e9+;
LL n, k; LL qp(LL a, LL b)
{
LL res = ;
while(b)
{
if(b & ) res = res * a % MOD;
a = a * a % MOD;
b >>= ;
}
return res;
} int main()
{
while(cin>> n >> k)
{
if(n == )
{
cout<< <<endl;
return ;
}
n %= MOD;
cout<< ((qp(, k+) * n % MOD - (qp(, k) - + MOD) % MOD) + MOD) % MOD <<endl;
} return ;
} //348612312017571993 87570063840727716