A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Consider a permutation p of length n, we build a graph of size n using it as follows: 

  * For every 1 ≤ i ≤ n, find the largest j such that 1 ≤ j < i and p_j > p_i, and add an undirected edge between node i and node j 
  * For every 1 ≤ i ≤ n, find the smallest j such that i < j ≤ n and p_j > p_i, and add an undirected edge between node i and node j 



In cases where no such j exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example n = 4, and p = [3,1,4,2]; here, the edges of the graph are (1,3),(2,1),(2,3),(4,3).

A permutation p is cyclic if the graph built using p has at least one simple cycle. 

Given n, find the number of cyclic permutations of length n. Since the number may be very large, output it modulo 10^9+7.

Please refer to the Notes section for the formal definition of a simple cycle

Input

The first and only line contains a single integer n (3 ≤ n ≤ 10^6).

Output

Output a single integer 0 ≤ x < 10^9+7, the number of cyclic permutations of length n modulo 10^9+7.

Examples

Input


4


Output


16

Input


583291


Output


135712853

Note

There are 16 cyclic permutations for n = 4. [4,2,1,3] is one such permutation, having a cycle of length four: 4 → 3 → 2 → 1 → 4.

Nodes v_1, v_2, …, v_k form a simple cycle if the following conditions hold: 

  * k ≥ 3. 
  * v_i ≠ v_j for any pair of indices i and j. (1 ≤ i < j ≤ k) 
  * v_i and v_{i+1} share an edge for all i (1 ≤ i < k), and v_1 and v_k share an edge. 
66
 652615
 482331
 336161
 33
 1000000
 79531
 768208
 3
 885131

257415584
 960319213
 722928541
 234634596
 762187807
 23581336
 162141608
 635322133
 2
 329995454


import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;

/**
 * Accomplished using the EduTools plugin by JetBrains https://plugins.jetbrains.com/plugin/10081-edutools
 */

public class Main {

	private static final int MOD = 1_000_000_007;

	public static void main(String[] args) throws Exception {
		try (InputUtil inputUtil = new InputUtil()) {
			solve(inputUtil, 0);
		}

	}

	private static void solve(InputUtil inputUtil, int t) throws Exception {
		int n = inputUtil.readLineAsInt();
		long nFactorial = LongStream.rangeClosed(1, n)
				.reduce(1, (a, b) -> (a * b) %  MOD);

		long uniformSequenceCount = BigInteger.valueOf(2).modPow(BigInteger.valueOf(n - 1), BigInteger.valueOf(MOD)).longValue();

		System.out.println((nFactorial - uniformSequenceCount + MOD) % MOD);
	}

	public static class InputUtil implements Closeable {

		private final BufferedReader reader;

		public InputUtil() throws Exception {
			this.reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String nextLine() throws IOException {
			return reader.readLine();
		}


		public int readLineAsInt() throws Exception {
			return Integer.parseInt(reader.readLine().trim());
		}

		public long readLineAsLong() throws Exception {
			return Long.parseLong(reader.readLine());
		}

		public String getSpaceSeperatedInts(int[] ints) {
			return Stream.of(ints)
					.map(String::valueOf)
					.collect(Collectors.joining(" "));
		}

		public String getSpaceSeperatedBigInteger(BigInteger[] nums) {
			return Stream.of(nums)
					.map(BigInteger::toString)
					.collect(Collectors.joining(" "));
		}

		public boolean isEven(long number) {
			return number % 2 == 0;
		}

		public boolean isOdd(long number) {
			return !isEven(number);
		}

		public boolean isEven(BigInteger number) {
			return !number.testBit(1);
		}

		public boolean isOdd(BigInteger number) {
			return !isEven(number);
		}

		public int[] readInts() throws IOException {
			return toIntArray(reader.readLine());
		}

		public int[] toIntArray(String s) {
			return Stream.of(s.split("\\s"))
					.mapToInt(Integer::parseInt)
					.toArray();
		}

		public long[] readLongs() throws IOException {
			return toLongArray(reader.readLine().trim());
		}

		public String[] readStrings() throws IOException {
			return reader.readLine().split("\\s");

		}


		public long[] toLongArray(String s) {
			return Stream.of(s.split("\\s"))
					.mapToLong(Long::parseLong)
					.toArray();
		}

		public BigInteger[] readBigInts() throws IOException {
			return toBigIntArray(reader.readLine());
		}

		public BigInteger[] toBigIntArray(String s) {
			String[] nums = s.split("\\s");
			return IntStream.range(0, nums.length)
					.boxed()
					.map(index -> new BigInteger(nums[index]))
					.toArray(size -> new BigInteger[size]);

		}

		public char[] readChars() throws IOException {
			return reader.readLine().toCharArray();
		}

		public BufferedReader getReader() {
			return reader;
		}

		@Override
		public void close() throws IOException {
			reader.close();
		}

	}

	public static class Pair<K, V> {

		public K first;

		public V second;

		public Pair(K first, V second) {
			this.first = first;
			this.second = second;
		}

		public Pair() {
		}

		public K getFirst() {
			return this.first;
		}

		public V getSecond() {
			return this.second;
		}

		@Override
		public String toString() {
			return "Pair [first=" + first + ", second=" + second + "]";
		}
	}

	public static class Util {

		public static int max(int... values) {
			int maxChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				maxChamp = Math.max(maxChamp, values[i]);
			}
			return maxChamp;
		}

		public static long max(long... values) {
			long maxChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				maxChamp = Math.max(maxChamp, values[i]);
			}
			return maxChamp;
		}

		public static int min(int... values) {
			int minChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				minChamp = Math.min(minChamp, values[i]);
			}
			return minChamp;
		}


		public static long min(long... values) {
			long minChamp = values[0];
			for (int i = 0; i < values.length; i++) {
				minChamp = Math.min(minChamp, values[i]);
			}
			return minChamp;
		}


		public static String getSpaceSeperatedInts(int[] ints) {
			return Arrays.stream(ints).mapToObj(i -> Integer.toString(i)).collect(Collectors.joining(" "));
		}

		public static String getSpaceSeperatedBigInteger(BigInteger[] nums) {
			return Stream.of(nums)
					.map(BigInteger::toString)
					.collect(Collectors.joining(" "));

		}

		public static boolean isEven(long number) {
			return number % 2 == 0;
		}

		public static boolean isOdd(long number) {
			return !isEven(number);
		}

		public static boolean isEven(BigInteger number) {
			return !number.testBit(1);
		}

		public static boolean isOdd(BigInteger number) {
			return !isEven(number);
		}

		public static int[] readInts(BufferedReader reader) throws IOException {
			return toIntArray(reader.readLine());
		}

		public static int[] toIntArray(String s) {
			return Stream.of(s.split("\\s")).mapToInt(Integer::parseInt).toArray();
		}

		public static long[] readLongs(BufferedReader reader) throws IOException {
			return toLongArray(reader.readLine());
		}

		public static long[] toLongArray(String s) {
			return Stream.of(s.split("\\s")).mapToLong(Long::parseLong).toArray();
		}

		public static BigInteger[] readBigInts(BufferedReader reader) throws IOException {
			return toBigIntArray(reader.readLine());
		}

		public static BigInteger[] toBigIntArray(String s) {
			String[] nums = s.split("\\s");
			return IntStream.range(0, nums.length)
					.boxed()
					.map(index -> new BigInteger(nums[index]))
					.toArray(size -> new BigInteger[size]);

		}

		public static int getMinIndex(int[] array) {
			return IntStream.range(0, array.length).reduce(0, (i, j) -> array[i] < array[j] ? i : array[i] > array[j] ? j : Math.min(i, j));
		}


		public static int getMaxIndex(int[] array) {
			return IntStream.range(0, array.length).reduce(0, (i, j) -> array[i] > array[j] ? i : array[i] < array[j] ? j : Math.min(i, j));
		}

		public static char[] readChars(BufferedReader reader) throws IOException {
			return reader.readLine().toCharArray();
		}

	}


}