There are N blocks arranged in a row, numbered 1 to N from left to right. Each block has a weight, and the weight of Block i is A_i. Snuke will perform the following operation on these blocks N times:

* Choose one block that is still not removed, and remove it. The cost of this operation is the sum of the weights of the blocks that are connected to the block being removed (including itself). Here, two blocks x and y ( x \leq y ) are connected when, for all z ( x \leq z \leq y ), Block z is still not removed.



There are N! possible orders in which Snuke removes the blocks. For all of those N! orders, find the total cost of the N operations, and calculate the sum of those N! total costs. As the answer can be extremely large, compute the sum modulo 10^9+7.

Constraints

* 1 \leq N \leq 10^5
* 1 \leq A_i \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

For all of the N! orders, find the total cost of the N operations, and print the sum of those N! total costs, modulo 10^9+7.

Examples

Input

2
1 2


Output

9


Input

4
1 1 1 1


Output

212


Input

10
1 2 4 8 16 32 64 128 256 512


Output

880971923
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class Main {
	
	static class ModuloCombinatorics {
		/** maximal needed number, N itself is included **/
		final int N;

		/** prime modulo **/
		final int P;

		/** factorials **/
		final int[] fact;

		/** multiplicative inverses, take care to not touch inv[0] **/
		final int[] inv;

		/** inverse factorials **/
		final int[] invFact;

		public ModuloCombinatorics(int N, int P) {
			this.N = N;
			this.P = P;
			fact = new int[N + 1];
			fact[0] = 1;
			for (int i = 1; i <= N; i++) {
				fact[i] = (int) ((long) i * fact[i - 1] % P);
			}

			inv = new int[N + 1];
			inv[1] = 1;
			for (int i = 2; i <= N; i++) {
				inv[i] = P - (int) ((long) (P / i) * inv[P % i] % P);
			}

			invFact = new int[N + 1];
			invFact[0] = 1;
			for (int i = 1; i <= N; i++) {
				invFact[i] = (int) ((long) invFact[i - 1] * inv[i] % P);
			}
		}

		public int choose(int n, int k) {
			return (n < 0 || k < 0 || k > n) ? 0 : (int) ((long) fact[n]
					* invFact[k] % P * invFact[n - k] % P);
		}

		/** a^b modulo mod, mod is arbitrary **/
		static public int pow(int a, long b, int mod) {
			if (a < 0 || a >= mod || b < 0) {
				throw new IllegalArgumentException();
			}
			int ret = 1;
			for (; b > 0; b >>= 1) {
				if ((b & 1) == 1) {
					ret = (int) ((long) ret * a % mod);
				}
				a = (int) ((long) a * a % mod);
			}
			return ret;
		}

		/** a^b modulo P **/
		public int pow(int a, long b) {
			return pow(a, b, P);
		}
	}
	
	static final int P = 1_000_000_007;

	void submit() {
		int n = nextInt();
		int[] a = new int[n];
		int[] b = new int[n + 1];
		
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
			b[i + 1] = b[i] + a[i];
			if (b[i + 1] >= P) {
				b[i + 1] -= P;
			}
		}
		
		ModuloCombinatorics mc = new ModuloCombinatorics(n + 10, P);
		
		int ans = 0;
		
		int[] sum = new int[mc.inv.length];

		for (int i = 3; i < sum.length; i++) {
			int delta = (int) (2L * mc.inv[i] % P * mc.inv[i - 1] % P);
			sum[i] = sum[i - 1] + delta;
			if (sum[i] >= P) {
				sum[i] -= P;
			}
		}
		
		for (int i = 1; i < n; i++) {
			int pos = sum[i + 1];
			int neg = sum[n + 1 - i];
			
			long delta = pos - neg;
			if (delta < 0) {
				delta += P;
			}
			
			delta = delta * b[i] % P;
			ans += delta;
			if (ans >= P) {
				ans -= P;
			}
		}
		
		ans = (int)((long)ans * mc.fact[n] % P);
		
//		System.err.println(ans);
		
		ans += (int)((long)b[n] * mc.fact[n] % P);
		if (ans >= P) {
			ans -= P;
		}
		
		for (int i = 1; i < n; i++) {
			int here1 = b[i];
			int here2 = b[n] - b[n - i];
			if (here2 < 0) {
				here2 += P;
			}
			
			int tot = here1 + here2;
			if (tot >= P) {
				tot -= P;
			}
			
			ans += (int)((long)tot * mc.fact[n] % P * mc.inv[i + 1] % P);
			if (ans >= P) {
				ans -= P;
			}
		}
		
		out.println(ans);
		
	}

	void test() {

	}

	void stress() {
		for (int tst = 0;; tst++) {
			if (false) {
				throw new AssertionError();
			}
			System.err.println(tst);
		}
	}

	Main() throws IOException {
		is = System.in;
		out = new PrintWriter(System.out);
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();
	static final int C = 5;

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	private InputStream is;
	PrintWriter out;

	private byte[] buf = new byte[1 << 14];
	private int bufSz = 0, bufPtr = 0;

	private int readByte() {
		if (bufSz == -1)
			throw new RuntimeException("Reading past EOF");
		if (bufPtr >= bufSz) {
			bufPtr = 0;
			try {
				bufSz = is.read(buf);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			if (bufSz <= 0)
				return -1;
		}
		return buf[bufPtr++];
	}

	private boolean isTrash(int c) {
		return c < 33 || c > 126;
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isTrash(b))
			;
		return b;
	}

	String nextToken() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	String nextString() {
		int b = readByte();
		StringBuilder sb = new StringBuilder();
		while (!isTrash(b) || b == ' ') {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	char nextChar() {
		return (char) skip();
	}

	int nextInt() {
		int ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}

	long nextLong() {
		long ret = 0;
		int b = skip();
		if (b != '-' && (b < '0' || b > '9')) {
			throw new InputMismatchException();
		}
		boolean neg = false;
		if (b == '-') {
			neg = true;
			b = readByte();
		}
		while (true) {
			if (b >= '0' && b <= '9') {
				ret = ret * 10 + (b - '0');
			} else {
				if (b != -1 && !isTrash(b)) {
					throw new InputMismatchException();
				}
				return neg ? -ret : ret;
			}
			b = readByte();
		}
	}
}
