prime-arrangements

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

Since the answer may be large, return the answer modulo <code>10^9 + 7</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
Input: n = 100
Output: 682289015
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>

numPrimeArrangements

Prime Arrangements

Math

请你帮忙给从 <code>1</code> 到 <code>n</code>&nbsp;的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod&nbsp;<code>10^9 + 7</code>&nbsp;之后的结果即可。

&nbsp;

示例 1：

<pre>输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
</pre>

示例 2：

<pre>输入：n = 100
输出：682289015
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>