Daily question: 1175 Prime permutation

Please help me to 1 To n  Number design arrangement scheme , Make all of 「 Prime number 」 Should be placed in 「 Prime index 」（ Index from 1 Start ） On ; You need to return the total number of possible solutions .

Let's review 「 Prime number 」： The prime number must be greater than 1 Of , And it cannot be expressed by the product of two positive integers less than it .

Because the answer could be big , So please return to the answer model mod 10^9 + 7  Then the result is .

Example 1：

Input ：n = 5
Output ：12
explain ： for instance ,[1,2,5,4,3] Is an effective arrangement , but [5,2,3,4,1] No , Because in the second case, prime numbers 5 It is wrongly placed in the index as 1 Location .
Example 2：

Input ：n = 100
Output ：682289015
 

Tips ：

1 <= n <= 100

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/prime-arrangements
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

class Solution {
public:
    bool vt[110];
    int primes[110];
    int numPrimeArrangements(int n) {
        int mod=1e9+7;
        int cnt=0;

        // Sieve prime number 
        for(int i=2;i<=n;i++){
            if(!vt[i]) primes[cnt++]=i;
            for(int j=0;primes[j]<=n/i;j++){
                vt[i*primes[j]]=true;
                if(i%primes[j]==0) break;
            }
        }
        long long sum=1;
        // Prime total permutation 
        for(int i=2;i<=cnt;i++){
            sum=(sum*i)%mod;
        }
        // Primes are all arranged 
        for(int i=n-cnt;i>1;i--){
            sum=(sum*i)%mod;
        }
        return sum;
    }
};