{"raw_statement":[{"iden":"statement","content":"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).\n\nUnfortunately, 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.\n\nNastya owns _x_ dresses now, so she became interested in the [expected number](https://en.wikipedia.org/wiki/Expected_value) of dresses she will have in one year. Nastya lives in Byteland, so the year lasts for _k_ + 1 months.\n\nNastya is really busy, so she wants you to solve this problem. You are the programmer, after all. Also, you should find the answer modulo 109 + 7, because it is easy to see that it is always integer."},{"iden":"input","content":"The only line contains two integers _x_ and _k_ (0 ≤ _x_, _k_ ≤ 1018), where _x_ is the initial number of dresses and _k_ + 1 is the number of months in a year in Byteland."},{"iden":"output","content":"In the only line print a single integer — the expected number of dresses Nastya will own one year later modulo 109 + 7."},{"iden":"examples","content":"Input\n\n2 0\n\nOutput\n\n4\n\nInput\n\n2 1\n\nOutput\n\n7\n\nInput\n\n3 2\n\nOutput\n\n21"},{"iden":"note","content":"In the first example a year consists on only one month, so the wardrobe does not eat dresses at all.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"Nastya 在新年收到了一份礼物——一个魔法衣橱。它的神奇之处在于，每个月末，衣橱中的连衣裙数量会翻倍（即变为月初数量的两倍）。\n\n不幸的是，每次翻倍后，衣橱会以 #cf_span[50%] 的概率吃掉一件连衣裙（如果有的话）。这一过程发生在一年中的每个月，除了最后一个月。\n\nNastya 目前拥有 #cf_span[x] 件连衣裙，她想知道一年后她拥有的连衣裙的期望数量。Nastya 居住在 Byteland，那里的一年持续 #cf_span[k + 1] 个月。\n\nNastya 非常忙碌，所以她希望你来解决这个问题。你可是程序员啊。此外，你应该对答案取模 #cf_span[109 + 7]，因为可以很容易看出答案始终是整数。\n\n输入仅一行包含两个整数 #cf_span[x] 和 #cf_span[k]（#cf_span[0 ≤ x, k ≤ 1018]），其中 #cf_span[x] 是初始的连衣裙数量，#cf_span[k + 1] 是 Byteland 一年的月份数。\n\n请在一行中输出一个整数——Nastya 一年后拥有的连衣裙的期望数量，对 #cf_span[109 + 7] 取模。\n\n在第一个例子中，一年只有一个月，因此衣橱不会吃掉任何连衣裙。\n\n在第二个例子中，第一个月结束后，有 #cf_span[50%] 的概率剩下 #cf_span[3] 件连衣裙，有 #cf_span[50%] 的概率剩下 #cf_span[4] 件连衣裙。因此，年末时有 #cf_span[50%] 的概率有 #cf_span[6] 件连衣裙，有 #cf_span[50%] 的概率有 #cf_span[8] 件连衣裙。因此该测试用例的答案为 #cf_span[(6 + 8) / 2 = 7]。"},{"iden":"input","content":"仅一行包含两个整数 #cf_span[x] 和 #cf_span[k]（#cf_span[0 ≤ x, k ≤ 1018]），其中 #cf_span[x] 是初始的连衣裙数量，#cf_span[k + 1] 是 Byteland 一年的月份数。"},{"iden":"output","content":"仅一行输出一个整数——Nastya 一年后拥有的连衣裙的期望数量，对 #cf_span[109 + 7] 取模。"},{"iden":"examples","content":"输入2 0输出4输入2 1输出7输入3 2输出21"},{"iden":"note","content":"在第一个例子中，一年只有一个月，因此衣橱不会吃掉任何连衣裙。\n\n在第二个例子中，第一个月结束后，有 #cf_span[50%] 的概率剩下 #cf_span[3] 件连衣裙，有 #cf_span[50%] 的概率剩下 #cf_span[4] 件连衣裙。因此，年末时有 #cf_span[50%] 的概率有 #cf_span[6] 件连衣裙，有 #cf_span[50%] 的概率有 #cf_span[8] 件连衣裙。因此该测试用例的答案为 #cf_span[(6 + 8) / 2 = 7]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ x $ be the initial number of dresses, and $ k+1 $ be the number of months in the year.\n\nDefine $ E_n $ as the expected number of dresses at the end of month $ n $, with $ E_0 = x $.\n\nFor each month $ i = 1, 2, \\dots, k $ (i.e., all months except the last), the process is:\n- Double the dresses: $ 2E_{i-1} $\n- Then, with probability $ \\frac{1}{2} $, one dress is eaten (if any), so:\n  $$\n  E_i = \\frac{1}{2} \\cdot (2E_{i-1}) + \\frac{1}{2} \\cdot (2E_{i-1} - 1) = 2E_{i-1} - \\frac{1}{2}\n  $$\n\nFor the final month (month $ k+1 $), there is no eating:\n$$\nE_{k+1} = 2E_k\n$$\n\nThus, we have the recurrence:\n- For $ 1 \\leq i \\leq k $: $ E_i = 2E_{i-1} - \\frac{1}{2} $\n- $ E_{k+1} = 2E_k $\n\nWe solve the recurrence for $ E_k $, then compute $ E_{k+1} $.\n\n---\n\n### Solving the recurrence:\n\nLet $ E_0 = x $\n\nFor $ i \\geq 1 $, define:\n$$\nE_i = 2E_{i-1} - \\frac{1}{2}\n$$\n\nThis is a linear nonhomogeneous recurrence. Solve it:\n\nHomogeneous solution: $ E_i^{(h)} = A \\cdot 2^i $\n\nParticular solution: Try constant $ C $. Plug in:\n$$\nC = 2C - \\frac{1}{2} \\Rightarrow C = \\frac{1}{2}\n$$\n\nGeneral solution:\n$$\nE_i = A \\cdot 2^i + \\frac{1}{2}\n$$\n\nUse initial condition $ E_0 = x $:\n$$\nx = A \\cdot 2^0 + \\frac{1}{2} \\Rightarrow A = x - \\frac{1}{2}\n$$\n\nThus:\n$$\nE_i = \\left(x - \\frac{1}{2}\\right) \\cdot 2^i + \\frac{1}{2}\n$$\n\nSo for $ i = k $:\n$$\nE_k = \\left(x - \\frac{1}{2}\\right) \\cdot 2^k + \\frac{1}{2}\n$$\n\nThen:\n$$\nE_{k+1} = 2E_k = 2\\left[\\left(x - \\frac{1}{2}\\right) \\cdot 2^k + \\frac{1}{2}\\right] = \\left(x - \\frac{1}{2}\\right) \\cdot 2^{k+1} + 1\n$$\n\nSimplify:\n$$\nE_{k+1} = x \\cdot 2^{k+1} - 2^k + 1\n$$\n\n---\n\n### Final Answer:\n\n$$\n\\boxed{E_{k+1} = x \\cdot 2^{k+1} - 2^k + 1}\n$$\n\nCompute this modulo $ 10^9 + 7 $, with $ x, k \\leq 10^{18} $.\n\nNote: All operations must be done modulo $ 10^9 + 7 $, using modular exponentiation and modular arithmetic.\n\nThus, the answer is:\n$$\n\\left( x \\cdot 2^{k+1} - 2^k + 1 \\right) \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}