K. The World of Trains

Codeforces

IDCF10113K

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

In the computer world, a train of the length n can be represented as an array A of the same length. Such an array A contains integer elements between 1 and k, inclusive. Each element in A represents the quality of one carriage. You can notice that there are exactly kn distinct trains. Mike loves to travel and today he is going to do it with his friends. They want to occupy exactly d consecutive carriages. Of course, they want chosen d carriages to be of equal quality. Someone saw a train and thus knows an array A. He said that there are exactly t ways for them to choose d consecutive carriages of equal quality. Now, Mike wants to know how many trains satisfy this description. Your task is to count them modulo 109 + 7. The only line of the input contains four integers n, d, t and k (1 ≤ d ≤ n ≤ 3333, 0 ≤ t ≤ n - d + 1, 1 ≤ k ≤ 109). Find the number of distinct trains fitting the given description, and print it modulo 109 + 7. For the first sample test the only possible arrays are: ## Input The only line of the input contains four integers n, d, t and k (1 ≤ d ≤ n ≤ 3333, 0 ≤ t ≤ n - d + 1, 1 ≤ k ≤ 109). ## Output Find the number of distinct trains fitting the given description, and print it modulo 109 + 7. [samples] ## Note For the first sample test the only possible arrays are: {1, 1, 2, 1, 2} {1, 2, 1, 1, 2} {1, 2, 1, 2, 2} {1, 2, 2, 1, 2} {2, 1, 1, 2, 1} {2, 1, 2, 1, 1} {2, 1, 2, 2, 1} {2, 2, 1, 2, 1}

**Definitions** Let $ n, d, t, k \in \mathbb{Z} $ be given integers with $ 1 \leq d \leq n \leq 3333 $, $ 0 \leq t \leq n - d + 1 $, $ 1 \leq k \leq 10^9 $. Let $ \mathcal{A} $ be the set of all sequences $ A = (a_1, a_2, \dots, a_n) $ where each $ a_i \in \{1, 2, \dots, k\} $. For a sequence $ A \in \mathcal{A} $, define the number of *valid windows* as: $$ f(A) = \left| \left\{ i \in \{1, 2, \dots, n - d + 1\} \mid a_i = a_{i+1} = \dots = a_{i+d-1} \right\} \right| $$ **Constraints** 1. $ 1 \leq d \leq n \leq 3333 $ 2. $ 0 \leq t \leq n - d + 1 $ 3. $ 1 \leq k \leq 10^9 $ **Objective** Compute: $$ \left| \left\{ A \in \mathcal{A} \mid f(A) = t \right\} \right| \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "K. The World of Trains",
    "description": {
      "content": "In the computer world, a train of the length n can be represented as an array A of the same length. Such an array A contains integer elements between 1 and k, inclusive. Each element in A represents t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10113K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the computer world, a train of the length n can be represented as an array A of the same length. Such an array A contains integer elements between 1 and k, inclusive. Each element in A represents t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, d, t, k \\in \\mathbb{Z} $ be given integers with $ 1 \\leq d \\leq n \\leq 3333 $, $ 0 \\leq t \\leq n - d + 1 $, $ 1 \\leq k \\leq 10^9 $.  \nLet $ \\mathcal{A} $ be the set of all s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments