D. Уголки

Codeforces

IDCF10144D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых квадратных клеточек, а второго разрезал на k уголков по три клеточки каждый. Теперь он интересуется вопросом: а сколько способов разместить эти уголки на полоске так, чтобы они не пересекались (то есть, чтобы ни одна клетка полосы не была покрыта более чем одним уголком). Петя не может отличить один уголок от другого, так что расстановки, отличающиеся только порядком уголков следует считать одинаковыми. Так как число способов может быть большим, а Петя добрый мальчик, ответ нужно вывести по модулю 109 + 7. Два натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109. Выведите единственное число – ответ на задачу. ## Входные Данные Два натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109. ## Выходные Данные Выведите единственное число – ответ на задачу. ## Примеры Входные данные2 1Выходные данные4Входные данные2 2Выходные данные0Входные данные3 2Выходные данные2Входные данные10 4Выходные данные5820 [samples]

**Definitions** Let $ k \in \mathbb{Z} $, $ 1 \leq k \leq 10^9 $. Let $ A = (A_1, A_2, \dots) $ be an infinite sequence of integers satisfying the recurrence: $$ A_{n+1} = A_n \quad \text{for all } n \geq 1, \quad \text{and} \quad A_{k+1} = A_1. $$ **Constraints** 1. $ A_{k+1} = A_1 $ 2. All $ A_i \in \mathbb{Z} $ 3. The sequence is constant: $ A_1 = A_2 = \cdots = A_{k+1} = x $ for some $ x \in \mathbb{Z} $ **Objective** Count the number of integer values $ x \in \mathbb{Z} $ such that the condition $ A_{k+1} = A_1 = x $ is satisfied. If infinitely many such $ x $ exist, output $ -1 $. Otherwise, output the count modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "D. Уголки",
    "description": {
      "content": "Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых кв",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10144D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых кв...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z} $, $ 1 \\leq k \\leq 10^9 $.  \nLet $ A = (A_1, A_2, \\dots) $ be an infinite sequence of integers satisfying the recurrence:  \n$$\nA_{n+1} = A_n \\quad \\text{for al...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments