1
class Solution {
2
 public:
3
  bool isPrime(int x) {
4
    if (x <= 3) return x > 1;
5
    if (x % 2 == 0) return false;
6

7
    for (int i = 3; i <= sqrt(x); i += 2) {
8
      if (x % i == 0) return false;
9
    }
10
    return true;
11
  }
12

13
  int fact(int x) {
14
    if (x <= 1) return 1;
15
    return ((long long)(x)*fact(x - 1)) % 1000000007;
16
  }
17

18
  int numPrimeArrangements(int n) {
19
    int c = 0;
20
    for (int i = 1; i <= n; ++i) {
21
      c += isPrime(i);
22
    }
23
    return ((long long)(fact(n - c)) * fact(c)) % 1000000007;
24
  }
25
};