- ← Back
- A
- B
- C
- D
- F
- Масиви1
- А обласна олімпіада 2024
- Проста
- В обласна 2024(масив!)
- А ОТГ 2023
- А обласна олімпіада 2023
- K
- L
- Е (sum)
- G(sum)
- Н(sum)
- І (кількість)
- J(Кількість)
- N(Кількість)
- А 2023 (проста)
- А 2017 (Стрічки)
- А 2018 (Стрічки)
- А 2012(Стрічки)
- Стрічки
- В 2022(Стрічки)
- Масив стрічок
- В 2023 Стрічки
- С 2023 ОТГ (масив стрічок)
- А 2021 проста
- B 2021
- В ОТГ 2023
- D 2023
- умови
- проста
- 2024 ОТГ В
- Масив стрічок
- Стрічки
- Множини D2024
- формули F 2023
- формули С 2024 ОТГ
- Формули 2023С
- Масиви C 2024
- Макс ІІ
- район2024
- область 25 а
- обл 25b
- Scoreboard
Гарна шеренга
Limits: 2 sec., 512 MiB
У Зеника з Марічкою на фермі є \(n\) жеребців, пронумерованих від \(1\) до \(n\).
Фермери хочуть вишикувати деяких своїх коней у шеренгу.
Назвемо шеренгу з \(k\) коней гарною, якщо всі коні в цій шерензі мають номери від \(1\) до \(k\) в будь-якому порядку.
Наприклад, шеренги \((2, 1, 3)\), \((1)\), \((4, 3, 2, 1)\) є гарними, а \((1, 2, 4, 5)\), \((47)\), \((3, 2)\) — ні.
Зеник та Марічка хочуть вибрати деяких своїх коней, та вишикувати їх у шеренгу. Порахуйте, будь ласка, скільки різних гарних шеренг вони можуть отримати. Дві шеренги вважаємо різними, якщо в них різна довжина, або на відповідних позиціях стоять коні з різними номерами. Оскільки ця кількість може бути дуже великою, виведіть остачу від її ділення на ціле число \(m\).
Input
В одному рядку задано два цілі числа \(n\) та \(m\).
Output
Виведіть ціле число — остачу від ділення кількості різних гарних шеренг на \(m\).
Constraints
\(1 \le n \le 10^9\),
\(1 \le m \le 1000\).
Оцінювання складається з таких блоків:
по 1 балу за кожен приклад з умови,
6 балів: \(m = 1\),
9 балів: \(n \le 10\),
23 бали: \(m = 10\),
17 балів: \(n \le 1000\),
42 бали: без додаткових обмежень.
Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 10 | 9 |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 7 | 5 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 777 | 474 |
Notes
У першому прикладі \(n=3, m=10\). Зеник і Марічка можуть вибрати коней і вишикувати їх у шеренгу \(15\) способами:
\((1)\) — гарна шеренга,
\((1, 2)\) — гарна шеренга,
\((1, 2, 3)\) — гарна шеренга,
\((1, 3)\),
\((1, 3, 2)\) — гарна шеренга,
\((2)\),
\((2, 1)\) — гарна шеренга,
\((2, 1, 3)\) — гарна шеренга,
\((2, 3)\),
\((2, 3, 1)\) — гарна шеренга,
\((3)\),
\((3, 1)\),
\((3, 1, 2)\) — гарна шеренга,
\((3, 2)\),
\((3, 2, 1)\) — гарна шеренга.
У дев’яти способах утворена шеренга є гарною. Відповідь — це остача від ділення \(9\) на \(10\), що дорівнює \(9\).
У другому прикладі \(n=4, m=7\). Зеник з Марічкою можуть утворити \(33\) гарні шеренги. Відповідь — це остача від ділення \(33\) на \(7\), що дорівнює \(5\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|