#1175

Prime Arrangements

pupil · 435 · lc easy +25 · verified · 60.8% accepted · 445 likes · top 60%

⚑ Combinatorics / Binomial Coefficients

Description

Count the permutations of integers 1 to n in which every prime number occupies a prime-numbered position (using 1-based indexing).

Recall that a prime is any integer greater than 1 whose only divisors are 1 and itself.

Since the answer can be enormous, return it modulo 109 + 7.

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

Code

1
2
3