1175. Prime Arrangements

Level - easy

Task

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Объяснение

Дана строка цифр, состоящая из первых 100 цифр числа π (пи) после запятой. Требуется найти количество перестановок этих цифр, в которых никакие две соседние цифры не являются простыми числами.

Пояснение:

1. Простые числа. Простые числа — это числа, которые делятся только на 1 и на себя. В данном контексте нас интересуют простые числа, которые могут быть цифрами: 2, 3, 5, 7.

2. Перестановки. Перестановка — это упорядоченный набор элементов, в котором каждый элемент используется ровно один раз. В данном случае мы рассматриваем перестановки цифр из строки.

3. Условие задачи. Необходимо найти количество перестановок, в которых никакие две соседние цифры не являются простыми. То есть, если в перестановке две соседние цифры — это простые числа (2, 3, 5 или 7), такая перестановка не подходит.

Возможное решение:

• Сгенерировать все возможные перестановки из 100 цифр.
• Проверить каждую перестановку на соответствие условию (никакие две соседние цифры не должны быть простыми).
• Подсчитать количество подходящих перестановок.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

• 1 <= n <= 100