{"raw_statement":[{"iden":"statement","content":"You have a team of _N_ people. For a particular task, you can pick any non-empty subset of people. The cost of having _x_ people for the task is _x__k_.\n\nOutput the sum of costs over all non-empty subsets of people."},{"iden":"input","content":"Only line of input contains two integers _N_ (1 ≤ _N_ ≤ 109) representing total number of people and _k_ (1 ≤ _k_ ≤ 5000)."},{"iden":"output","content":"Output the sum of costs for all non empty subsets modulo 109 + 7."},{"iden":"examples","content":"Input\n\n1 1\n\nOutput\n\n1\n\nInput\n\n3 2\n\nOutput\n\n24"},{"iden":"note","content":"In the first example, there is only one non-empty subset {1} with cost 11 = 1.\n\nIn the second example, there are seven non-empty subsets.\n\n\\- {1} with cost 12 = 1\n\n\\- {2} with cost 12 = 1\n\n\\- {1, 2} with cost 22 = 4\n\n\\- {3} with cost 12 = 1\n\n\\- {1, 3} with cost 22 = 4\n\n\\- {2, 3} with cost 22 = 4\n\n\\- {1, 2, 3} with cost 32 = 9\n\nThe total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24."}],"translated_statement":[{"iden":"statement","content":"你有一个由 #cf_span[N] 个人组成的团队。对于某个特定任务，你可以选择任意非空子集的人。让 #cf_span[x] 个人参与任务的成本是 #cf_span[xk]。\n\n请输出所有非空子集的成本之和。\n\n输入仅有一行，包含两个整数 #cf_span[N] #cf_span[(1 ≤ N ≤ 109)]，分别表示总人数和 #cf_span[k] #cf_span[(1 ≤ k ≤ 5000)]。\n\n请输出所有非空子集的成本之和对 #cf_span[109 + 7] 取模的结果。\n\n在第一个例子中，只有一个非空子集 #cf_span[{1}]，其成本为 #cf_span[11 = 1]。\n\n在第二个例子中，有七个非空子集：\n\n- #cf_span[{1}]，成本为 #cf_span[12 = 1]\n\n- #cf_span[{2}]，成本为 #cf_span[12 = 1]\n\n- #cf_span[{1, 2}]，成本为 #cf_span[22 = 4]\n\n- #cf_span[{3}]，成本为 #cf_span[12 = 1]\n\n- #cf_span[{1, 3}]，成本为 #cf_span[22 = 4]\n\n- #cf_span[{2, 3}]，成本为 #cf_span[22 = 4]\n\n- #cf_span[{1, 2, 3}]，成本为 #cf_span[32 = 9]\n\n总成本为 #cf_span[1 + 1 + 4 + 1 + 4 + 4 + 9 = 24]。\n\n"},{"iden":"input","content":"输入仅有一行，包含两个整数 #cf_span[N] #cf_span[(1 ≤ N ≤ 109)]，分别表示总人数和 #cf_span[k] #cf_span[(1 ≤ k ≤ 5000)]。"},{"iden":"output","content":"请输出所有非空子集的成本之和对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入1 1输出1输入3 2输出24"},{"iden":"note","content":"在第一个例子中，只有一个非空子集 #cf_span[{1}]，其成本为 #cf_span[11 = 1]。在第二个例子中，有七个非空子集：\n- #cf_span[{1}]，成本为 #cf_span[12 = 1]\n- #cf_span[{2}]，成本为 #cf_span[12 = 1]\n- #cf_span[{1, 2}]，成本为 #cf_span[22 = 4]\n- #cf_span[{3}]，成本为 #cf_span[12 = 1]\n- #cf_span[{1, 3}]，成本为 #cf_span[22 = 4]\n- #cf_span[{2, 3}]，成本为 #cf_span[22 = 4]\n- #cf_span[{1, 2, 3}]，成本为 #cf_span[32 = 9]\n总成本为 #cf_span[1 + 1 + 4 + 1 + 4 + 4 + 9 = 24]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 1 \\leq N \\leq 10^9 $, be the number of people.  \nLet $ k \\in \\mathbb{Z} $, $ 1 \\leq k \\leq 5000 $, be the cost exponent.  \nThe cost of a subset of size $ x $ is $ x^k $.  \n\n**Constraints**  \n- $ 1 \\leq N \\leq 10^9 $  \n- $ 1 \\leq k \\leq 5000 $  \n\n**Objective**  \nCompute the sum of costs over all non-empty subsets of the $ N $ people:  \n$$\n\\sum_{x=1}^{N} \\binom{N}{x} x^k \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}