1
class Solution {
2
  long mod = (long) (1e9 + 7);
3

4
  public int numPrimeArrangements(int n) {
5
    if (n == 1) {
6
      return 1;
7
    }
8

9
    boolean[] arr = new boolean[n + 1];
10
    Arrays.fill(arr, true);
11
    arr[0] = false;
12
    arr[1] = false;
13

14
    for (int i = 2; i <= Math.sqrt(n); i++) {
15

16
      for (int j = i * i; j <= n; j += i) {
17
        if (arr[i] == false) {
18
          continue;
19
        }
20
        arr[j] = false;
21
      }
22
    }
23
    long prime = 0;
24
    long notPrime = 0;
25
    for (int k = 1; k < arr.length; k++) {
26
      if (arr[k] == true) {
27
        prime++;
28
      } else {
29
        notPrime++;
30
      }
31
    }
32

33
    long x = factorial(prime) % mod;
34
    long y = factorial(notPrime) % mod;
35
    long t = (x * y) % mod;
36
    return (int) t;
37
  }
38

39
  public long factorial(long i) {
40
    if (i <= 1) {
41
      return i;
42
    }
43
    return (i * (factorial(i - 1) % mod)) % mod;
44
  }
45
}