E. Team Work

Codeforces

IDCF932E

Time2000ms

Memory256MB

Difficulty—

combinatoricsdpmath

English · Original

Chinese · Translation

Formal · Original

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 subsets of people. ## Input Only line of input contains two integers _N_ (1 ≤ _N_ ≤ 109) representing total number of people and _k_ (1 ≤ _k_ ≤ 5000). ## Output Output the sum of costs for all non empty subsets modulo 109 + 7. [samples] ## Note In the first example, there is only one non-empty subset {1} with cost 11 = 1. In the second example, there are seven non-empty subsets. \- {1} with cost 12 = 1 \- {2} with cost 12 = 1 \- {1, 2} with cost 22 = 4 \- {3} with cost 12 = 1 \- {1, 3} with cost 22 = 4 \- {2, 3} with cost 22 = 4 \- {1, 2, 3} with cost 32 = 9 The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

你有一个由 #cf_span[N] 个人组成的团队。对于某个特定任务，你可以选择任意非空子集的人。让 #cf_span[x] 个人参与任务的成本是 #cf_span[xk]。请输出所有非空子集的成本之和。输入仅有一行，包含两个整数 #cf_span[N] #cf_span[(1 ≤ N ≤ 109)]，分别表示总人数和 #cf_span[k] #cf_span[(1 ≤ k ≤ 5000)]。请输出所有非空子集的成本之和对 #cf_span[109 + 7] 取模的结果。在第一个例子中，只有一个非空子集 #cf_span[{1}]，其成本为 #cf_span[11 = 1]。在第二个例子中，有七个非空子集： - #cf_span[{1}]，成本为 #cf_span[12 = 1] - #cf_span[{2}]，成本为 #cf_span[12 = 1] - #cf_span[{1, 2}]，成本为 #cf_span[22 = 4] - #cf_span[{3}]，成本为 #cf_span[12 = 1] - #cf_span[{1, 3}]，成本为 #cf_span[22 = 4] - #cf_span[{2, 3}]，成本为 #cf_span[22 = 4] - #cf_span[{1, 2, 3}]，成本为 #cf_span[32 = 9] 总成本为 #cf_span[1 + 1 + 4 + 1 + 4 + 4 + 9 = 24]。 ## Input 输入仅有一行，包含两个整数 #cf_span[N] #cf_span[(1 ≤ N ≤ 109)]，分别表示总人数和 #cf_span[k] #cf_span[(1 ≤ k ≤ 5000)]。 ## Output 请输出所有非空子集的成本之和对 #cf_span[109 + 7] 取模的结果。 [samples] ## Note 在第一个例子中，只有一个非空子集 #cf_span[{1}]，其成本为 #cf_span[11 = 1]。在第二个例子中，有七个非空子集： - #cf_span[{1}]，成本为 #cf_span[12 = 1] - #cf_span[{2}]，成本为 #cf_span[12 = 1] - #cf_span[{1, 2}]，成本为 #cf_span[22 = 4] - #cf_span[{3}]，成本为 #cf_span[12 = 1] - #cf_span[{1, 3}]，成本为 #cf_span[22 = 4] - #cf_span[{2, 3}]，成本为 #cf_span[22 = 4] - #cf_span[{1, 2, 3}]，成本为 #cf_span[32 = 9] 总成本为 #cf_span[1 + 1 + 4 + 1 + 4 + 4 + 9 = 24]。

**Definitions** Let $ N \in \mathbb{Z} $, $ 1 \leq N \leq 10^9 $, be the number of people. Let $ k \in \mathbb{Z} $, $ 1 \leq k \leq 5000 $, be the cost exponent. The cost of a subset of size $ x $ is $ x^k $. **Constraints** - $ 1 \leq N \leq 10^9 $ - $ 1 \leq k \leq 5000 $ **Objective** Compute the sum of costs over all non-empty subsets of the $ N $ people: $$ \sum_{x=1}^{N} \binom{N}{x} x^k \mod (10^9 + 7) $$

Samples

Input #1

1 1

Output #1

Input #2

3 2

Output #2

API Response (JSON)

{
  "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 sub...",
      "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)...",
      "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 $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments