{"problem":{"name":"E. Team Work","description":{"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_. Output the sum of costs over all non-empty sub","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF932E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nOnly line of input contains two integers _N_ (1 ≤ _N_ ≤ 109) representing total number of people and _k_ (1 ≤ _k_ ≤ 5000).\n\n## Output\n\nOutput the sum of costs for all non empty subsets modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n输入仅有一行，包含两个整数 #cf_span[N] #cf_span[(1 ≤ N ≤ 109)]，分别表示总人数和 #cf_span[k] #cf_span[(1 ≤ k ≤ 5000)]。\n\n## Output\n\n请输出所有非空子集的成本之和对 #cf_span[109 + 7] 取模的结果。\n\n[samples]\n\n## Note\n\n在第一个例子中，只有一个非空子集 #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]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF932E","tags":["combinatorics","dp","math"],"sample_group":[["1 1","1"],["3 2","24"]],"created_at":"2026-03-03 11:00:39"}}