1414: Красиві перестановки


Submit solution


Points:8
Time limit:1.0s
Memory limit:62M
Author:

Problem type

Перестановкою розміру n називається масив a1, a2,…, an різних чисел від 1 до n. Кожне число в перестановці зустрічається рівно один раз. Василько називає красотою перестановки a1, a2 ,…, an число (a1·a2 + a2·a3 + …+ a(n−1)·an ). Він хоче порахувати кількість перестановок, красота яких ділиться на k. Дано числа n та k, знайдіть кількість перестановок розміру n, красивість яких ділиться на k.

Наприклад, для n = 3 існує 6 перестановок. Розглянемо всі ці перестановки та їх красоту.

Перестановка      Красота
1, 2, 3     - 1 · 2 + 2 · 3 = 8
1, 3, 2     - 1 · 3 + 3 · 2 = 9
2, 1, 3     - 2 · 1 + 1 · 3 = 5
2, 3, 1     - 2 · 3 + 3 · 1 = 9
3, 1, 2     - 3 · 1 + 1 · 2 = 5
3, 2, 1     - 3 · 2 + 2 · 1 = 8

Формат вхідних даних

Вхідні дані містять два цілих числа: n та k (1 ≤ n ≤ 10, 2 ≤ k ≤ 1000).

Формат вихідних даних

Виведіть одне ціле число: кількість перестановок розміру n, красота яких ділиться на k.

Приклад вхідних даних

3 2

Приклад вихідних даних

2

Comments

There are no comments at the moment.