import java.util.*;
import java.io.*;
import java.math.*;
import java.util.function.*;
public class Main implements Runnable {
	static boolean DEBUG;
	public static void main(String[] args) {
		DEBUG = args.length > 0 && args[0].equals("-DEBUG");
		Thread.setDefaultUncaughtExceptionHandler((t, e) -> { e.printStackTrace(); System.exit(1); });
		new Thread(null, new Main(), "", 1 << 31).start();
	}

	public void run() {
		Solver solver = new Solver();
		solver.solve();
		solver.exit();
	}

	static class FastScanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int pointer = 0;
		private int buflen = 0;
		private boolean hasNextByte() {
			if(pointer < buflen) return true;
			else {
				pointer = 0;
				try {
					buflen = in.read(buffer);
				}catch (IOException e) {
					e.printStackTrace();
				}
				return buflen > 0;
			}
		}
		private int readByte() { if(hasNextByte()) return buffer[pointer ++]; else return -1; }
		private boolean isPrintableChar(int c) { return isPrintableChar(c, false); }
		private boolean isPrintableChar(int c, boolean includingSpace) { return (includingSpace ? 32 : 33) <= c && c <= 126; }
		private void skipUnprintable() { skipUnprintable(false); }
		private void skipUnprintable(boolean includingSpace) { while(hasNextByte() && !isPrintableChar(buffer[pointer], includingSpace)) pointer++; }
		private boolean hasNext() { return hasNext(false); }
		private boolean hasNext(boolean includingSpace) { skipUnprintable(includingSpace); return hasNextByte(); }
		private StringBuilder sb = new StringBuilder();
		public String next() { return next(false); }
		public String next(boolean includingSpace) {
			if(!hasNext(includingSpace)) throw new NoSuchElementException();
			sb.setLength(0);
			int b = readByte();
			while(isPrintableChar(b, includingSpace)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
		public long nextLong() {
			if(!hasNext()) throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if(b == '-') {
				minus = true;
				b = readByte();
			}
			if(b < '0' || '9' < b) throw new NumberFormatException();
			while(true) {
				if('0' <= b && b <= '9') n = n * 10 + b - '0';
				else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
	}

	static class Solver {
		FastScanner sc = new FastScanner();
		public Solver() { }

		String ns() { return ns(false); }
		String ns(boolean includingSpace) { return sc.next(includingSpace); }
		String[] ns(int n) { return ns(n, false); }
		String[] ns(int n, boolean includingSpace) {
			String a[] = new String[n];
			for(int i = 0; i < n; i ++) a[i] = ns(includingSpace);
			return a;
		}
		String[][] ns(int n, int m) { return ns(n, m, false); }
		String[][] ns(int n, int m, boolean includingSpace) {
			String a[][] = new String[n][m];
			for(int i = 0; i < n; i ++) a[i] = ns(m, includingSpace);
			return a;
		}
		char nc() { return ns().charAt(0); }
		char[] nc(int n) {
			String str = ns();
			if(n < 0) n = str.length();
			char a[] = new char[n];
			for(int i = 0; i < n; i ++) a[i] = str.charAt(i);
			return a;
		}
		char[][] nc(int n, int m) {
			char a[][] = new char[n][m];
			for(int i = 0; i < n; i ++) a[i] = nc(m);
			return a;
		}
		boolean[] nb(int n, char t) {
			char c[] = nc(-1);
			if(n < 0) n = c.length;
			boolean a[] = new boolean[n];
			for(int i = 0; i < n; i ++) a[i] = c[i] == t;
			return a;
		}
		boolean[][] nb(int n, int m, char t) {
			boolean a[][] = new boolean[n][m];
			for(int i = 0; i < n; i ++) a[i] = nb(m, t);
			return a;
		}
		int ni() { return Math.toIntExact(sc.nextLong()); }
		int[] ni(int n) {
			int a[] = new int[n];
			for(int i = 0; i < n; i ++) a[i] = ni();
			return a;
		}
		int[][] ni(int n, int m) {
			int a[][] = new int[n][m];
			for(int i = 0; i < n; i ++) a[i] = ni(m);
			return a;
		}
		long nl() { return sc.nextLong(); }
		long[] nl(int n) {
			long a[] = new long[n];
			for(int i = 0; i < n; i ++) a[i] = nl();
			return a;
		}
		long[][] nl(int n, int m) {
			long a[][] = new long[n][m];
			for(int i = 0; i < n; i ++) a[i] = nl(m);
			return a;
		}
		double nd() { return Double.parseDouble(sc.next()); }
		double[] nd(int n) {
			double a[] = new double[n];
			for(int i = 0; i < n; i ++) a[i] = nd();
			return a;
		}
		double[][] nd(int n, int m) {
			double a[][] = new double[n][m];
			for(int i = 0; i < n; i ++) a[i] = nd(m);
			return a;
		}

		String booleanToString(boolean b) { return b ? "#" : "."; }

		PrintWriter out = new PrintWriter(System.out);
		PrintWriter err = new PrintWriter(System.err);
		StringBuilder sb4prtln = new StringBuilder();
		void prt() { out.print(""); }
		<T> void prt(T a) { out.print(a); }
		void prtln() { out.println(""); }
		<T> void prtln(T a) { out.println(a); }
		void prtln(int... a) {
			sb4prtln.setLength(0);
			for(int element : a) sb4prtln.append(element+" ");
			prtln(sb4prtln.toString().trim());
		}
		void prtln(long... a) {
			sb4prtln.setLength(0);
			for(long element : a) sb4prtln.append(element+" ");
			prtln(sb4prtln.toString().trim());
		}
		void prtln(double... a) {
			sb4prtln.setLength(0);
			for(double element : a) sb4prtln.append(element+" ");
			prtln(sb4prtln.toString().trim());
		}
		void prtln(String... a) {
			sb4prtln.setLength(0);
			for(String element : a) sb4prtln.append(element+" ");
			prtln(sb4prtln.toString().trim());
		}
		void prtln(char... a) {
			sb4prtln.setLength(0);
			for(char element : a) sb4prtln.append(element);
			prtln(sb4prtln.toString());
		}
		void prtln(boolean... a) {
			sb4prtln.setLength(0);
			for(boolean element : a) sb4prtln.append(booleanToString(element));
			prtln(sb4prtln.toString());
		}
		void prtln(int[][] a) { for(int[] element : a) prtln(element); }
		void prtln(long[][] a) { for(long[] element : a) prtln(element); }
		void prtln(double[][] a) { for(double[] element : a) prtln(element); }
		void prtln(String[][] a) { for(String[] element : a) prtln(element); }
		void prtln(char[][] a) { for(char[] element : a) prtln(element); }
		void prtln(boolean[][] a) { for(boolean[] element : a) prtln(element); }

		String errconvert(int a) { return isINF(a) ? "_" : String.valueOf(a); }
		String errconvert(long a) { return isINF(a) ? "_" : String.valueOf(a); }
		void errprt(int a) { if(DEBUG) err.print(errconvert(a)); }
		void errprt(long a) { if(DEBUG) err.print(errconvert(a)); }
		void errprt() { if(DEBUG) err.print(""); }
		<T> void errprt(T a) { if(DEBUG) err.print(a); }
		void errprt(boolean a) { if(DEBUG) errprt(booleanToString(a)); }
		void errprtln() { if(DEBUG) err.println(""); }
		void errprtln(int a) { if(DEBUG) err.println(errconvert(a)); }
		void errprtln(long a) { if(DEBUG) err.println(errconvert(a)); }
		<T> void errprtln(T a) { if(DEBUG) err.println(a); }
		void errprtln(boolean a) { if(DEBUG) errprtln(booleanToString(a)); }
		void errprtln(int... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(int element : a) sb4prtln.append(errconvert(element)+" ");
				errprtln(sb4prtln.toString().trim());
			}
		}
		void errprtln(long... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(long element : a) sb4prtln.append(errconvert(element)+" ");
				errprtln(sb4prtln.toString().trim());
			}
		}
		void errprtln(double... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(double element : a) sb4prtln.append(element+" ");
				errprtln(sb4prtln.toString().trim());
			}
		}
		void errprtln(String... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(String element : a) sb4prtln.append(element+" ");
				errprtln(sb4prtln.toString().trim());
			}
		}
		void errprtln(char... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(char element : a) sb4prtln.append(element);
				errprtln(sb4prtln.toString());
			}
		}
		void errprtln(boolean... a) {
			if(DEBUG) {
				sb4prtln.setLength(0);
				for(boolean element : a) sb4prtln.append(booleanToString(element));
				errprtln(sb4prtln.toString());
			}
		}
		void errprtln(Object[] a) { if(DEBUG) for(Object element : a) errprtln(element); }
		void errprtln(int[][] a) { if(DEBUG) for(int[] element : a) errprtln(element); }
		void errprtln(long[][] a) { if(DEBUG) for(long[] element : a) errprtln(element); }
		void errprtln(double[][] a) { if(DEBUG) for(double[] element : a) errprtln(element); }
		void errprtln(String[][] a) { if(DEBUG) for(String[] element : a) errprtln(element); }
		void errprtln(char[][] a) { if(DEBUG) for(char[] element : a) errprtln(element); }
		void errprtln(boolean[][] a) { if(DEBUG) for(boolean[] element : a) errprtln(element); }
		void errprtln(Object[][] a) { if(DEBUG) for(Object element : a) { errprtln(element); errprtln(); } }

		void reply(boolean b) { prtln(b ? "Yes" : "No"); }
		void REPLY(boolean b) { prtln(b ? "YES" : "NO"); }

		void flush() { out.flush(); if(DEBUG) err.flush(); }
		void assertion(boolean b) { if(!b) { flush(); throw new AssertionError(); } }

		void exit() { flush(); System.exit(0); }
		<T> void exit(T a) { prtln(a); exit(); }
		void exit(int... a) { prtln(a); exit(); }
		void exit(long... a) { prtln(a); exit(); }
		void exit(double... a) { prtln(a); exit(); }
		void exit(String... a) { prtln(a); exit(); }
		void exit(char... a) { prtln(a); exit(); }
		void exit(boolean... a) { prtln(a); exit(); }
		void exit(int[][] a) { prtln(a); exit(); }
		void exit(long[][] a) { prtln(a); exit(); }
		void exit(double[][] a) { prtln(a); exit(); }
		void exit(String[][] a) { prtln(a); exit(); }
		void exit(char[][] a) { prtln(a); exit(); }
		void exit(boolean[][] a) { prtln(a); exit(); }


		final long INF = (long)1e18 + 7;
		boolean isPlusINF(long a) { return a > INF / 10; }
		boolean isMinusINF(long a) { return isPlusINF(- a); }
		boolean isINF(long a) { return isPlusINF(a) || isMinusINF(a); }
		final int I_INF = (int)1e9 + 7;
		boolean isPlusINF(int a) { return a > I_INF / 10; }
		boolean isMinusINF(int a) { return isPlusINF(- a); }
		boolean isINF(int a) { return isPlusINF(a) || isMinusINF(a); }


		int min(int a, int b) { return Math.min(a, b); }
		long min(long a, long b) { return Math.min(a, b); }
		double min(double a, double b) { return Math.min(a, b); }
		<T extends Comparable<T>> T min(T a, T b) { return a.compareTo(b) <= 0 ? a : b; }
		int min(int... x) {
			int min = x[0];
			for(int val : x) min = min(min, val);
			return min;
		}
		long min(long... x) {
			long min = x[0];
			for(long val : x) min = min(min, val);
			return min;
		}
		double min(double... x) {
			double min = x[0];
			for(double val : x) min = min(min, val);
			return min;
		}
		int max(int a, int b) { return Math.max(a, b); }
		long max(long a, long b) { return Math.max(a, b); }
		double max(double a, double b) { return Math.max(a, b); }
		<T extends Comparable<T>> T max(T a, T b) { return a.compareTo(b) >= 0 ? a : b; }
		int max(int... x) {
			int max = x[0];
			for(int val : x) max = max(max, val);
			return max;
		}
		long max(long... x) {
			long max = x[0];
			for(long val : x) max = max(max, val);
			return max;
		}
		double max(double... x) {
			double max = x[0];
			for(double val : x) max = max(max, val);
			return max;
		}
		<T extends Comparable<T>> T max(T[] x) {
			T max = x[0];
			for(T val : x) max = max(max, val);
			return max;
		}
		int max(int[][] a) {
			int max = a[0][0];
			for(int[] ele : a) max = max(max, max(ele));
			return max;
		}
		long max(long[][] a) {
			long max = a[0][0];
			for(long[] ele : a) max = max(max, max(ele));
			return max;
		}
		double max(double[][] a) {
			double max = a[0][0];
			for(double[] ele : a) max = max(max, max(ele));
			return max;
		}
		<T extends Comparable<T>> T max(T[][] a) {
			T max = a[0][0];
			for(T[] ele : a) max = max(max, max(ele));
			return max;
		}
		long sum(int... a) {
			long sum = 0;
			for(int element : a) sum += element;
			return sum;
		}
		long sum(long... a) {
			long sum = 0;
			for(long element : a) sum += element;
			return sum;
		}
		double sum(double... a) {
			double sum = 0;
			for(double element : a) sum += element;
			return sum;
		}
		long sum(boolean... a) {
			long sum = 0;
			for(boolean element : a) sum += element ? 1 : 0;
			return sum;
		}
		long[] sums(int[] a) {
			long sum[] = new long[a.length + 1];
			sum[0] = 0;
			for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i];
			return sum;
		}
		long[] sums(long[] a) {
			long sum[] = new long[a.length + 1];
			sum[0] = 0;
			for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i];
			return sum;
		}
		double[] sums(double[] a) {
			double sum[] = new double[a.length + 1];
			sum[0] = 0;
			for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + a[i];
			return sum;
		}
		long[] sums(boolean[] a) {
			long sum[] = new long[a.length + 1];
			sum[0] = 0;
			for(int i = 0; i < a.length; i ++) sum[i + 1] = sum[i] + (a[i] ? 1 : 0);
			return sum;
		}
		long[][] sums(int[][] a) {
			long sum[][] = new long[a.length + 1][a[0].length + 1];
			fill(sum, 0);
			for(int i = 0; i < a.length; i ++) {
				for(int j = 0; j < a[i].length; j ++) {
					sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
				}
			}
			return sum;
		}
		long[][] sums(long[][] a) {
			long sum[][] = new long[a.length + 1][a[0].length + 1];
			fill(sum, 0);
			for(int i = 0; i < a.length; i ++) {
				for(int j = 0; j < a[i].length; j ++) {
					sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
				}
			}
			return sum;
		}
		double[][] sums(double[][] a) {
			double sum[][] = new double[a.length + 1][a[0].length + 1];
			fill(sum, 0);
			for(int i = 0; i < a.length; i ++) {
				for(int j = 0; j < a[i].length; j ++) {
					sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
				}
			}
			return sum;
		}
		long[][] sums(boolean[][] a) {
			long sum[][] = new long[a.length + 1][a[0].length + 1];
			fill(sum, 0);
			for(int i = 0; i < a.length; i ++) {
				for(int j = 0; j < a[i].length; j ++) {
					sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (a[i][j] ? 1 : 0);
				}
			}
			return sum;
		}
		int constrain(int x, int l, int r) { return min(max(x, min(l, r)), max(l, r)); }
		long constrain(long x, long l, long r) { return min(max(x, min(l, r)), max(l, r)); }
		double constrain(double x, double l, double r) { return min(max(x, min(l, r)), max(l, r)); }
		int abs(int x) { return x >= 0 ? x : - x; }
		long abs(long x) { return x >= 0 ? x : - x; }
		double abs(double x) { return x >= 0 ? x : - x; }
		int signum(int x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		int signum(long x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		int signum(double x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
		long round(double x) { return Math.round(x); }
		long floor(double x) { return (long)Math.floor(x); }
		int divfloor(int a, int b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }
		long divfloor(long a, long b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }
		long ceil(double x) { return (long)Math.ceil(x); }
		int divceil(int a, int b) { return a >= 0 && b > 0 ? (a + b - 1) / b
											: a < 0 && b < 0 ? divceil(abs(a), abs(b))
											: - divfloor(abs(a), abs(b)); }
		long divceil(long a, long b) { return a >= 0 && b > 0 ? (a + b - 1) / b
											: a < 0 && b < 0 ? divceil(abs(a), abs(b))
											: - divfloor(abs(a), abs(b)); }
		double sqrt(int x) { return Math.sqrt((double)x); }
		double sqrt(long x) { return Math.sqrt((double)x); }
		double sqrt(double x) { return Math.sqrt(x); }
		long fact(int n) {
			long ans = 1;
			for(int i = 1; i <= n; i ++) ans = Math.multiplyExact(ans, i);
			return ans;
		}
		double pow(double x, double y) { return Math.pow(x, y); }
		long pow(long x, long y) {
			long ans = 1;
			while(true) {
				if(y % 2 != 0) ans = Math.multiplyExact(ans, x);
				y /= 2;
				if(y <= 0) return ans;
				x = Math.multiplyExact(x, x);
			}
		}
		int gcd(int a, int b) {
			while(true) {
				if(b == 0) return a;
				int tmp = a;
				a = b;
				b = tmp % b;
			}
		}
		long gcd(long a, long b) {
			while(true) {
				if(b == 0) return a;
				long tmp = a;
				a = b;
				b = tmp % b;
			}
		}
		long lcm(long a, long b) { return a / gcd(a, b) * b; }
		int gcd(int... a) {
			int gcd = 0;
			for(int i = 0; i < a.length; i ++) gcd = gcd(gcd, a[i]);
			return gcd;
		}
		long gcd(long... a) {
			long gcd = 0;
			for(int i = 0; i < a.length; i ++) gcd = gcd(gcd, a[i]);
			return gcd;
		}
		double random() { return Math.random(); }
		int random(int max) { return (int)floor(random() * max); }
		long random(long max) { return floor(random() * max); }
		double random(double max) { return random() * max; }
		int random(int min, int max) { return random(max - min) + min; }
		long random(long min, long max) { return random(max - min) + min; }
		double random(double min, double max) { return random(max - min) + min; }

		boolean isUpper(char a) { return a >= 'A' && a <= 'Z'; }
		boolean isLower(char a) { return a >= 'a' && a <= 'z'; }
		int upperToInt(char a) { return a - 'A'; }
		int lowerToInt(char a) { return a - 'a'; }
		int numToInt(char a) { return a - '0'; }
		int charToInt(char a) { return a >= 'a' ? lowerToInt(a) : a >= 'A' ? upperToInt(a) : numToInt(a); }
		char intToUpper(int a) { return (char)(a + 'A'); }
		char intToLower(int a) { return (char)(a + 'a'); }
		char intToNum(int a) { return (char)(a + '0'); }
		int[] charToInt(char[] a) {
			int array[] = new int[a.length];
			for(int i = 0; i < a.length; i ++) array[i] = charToInt(a[i]);
			return array;
		}

		int numDigits(long a) { return Long.toString(a).length(); }
		long bitFlag(int a) { return 1L << (long)a; }
		boolean isFlagged(long x, int a) { return (x & bitFlag(a)) != 0; }

		long countString(String str, String a) { return (str.length() - str.replace(a, "").length()) / a.length(); }
		long countStringAll(String str, String a) { return str.length() - str.replaceAll(a, "").length(); }

		void fill(int[] array, int x) { Arrays.fill(array, x); }
		void fill(long[] array, long x) { Arrays.fill(array, x); }
		void fill(double[] array, double x) { Arrays.fill(array, x); }
		void fill(char[] array, char x) { Arrays.fill(array, x); }
		void fill(boolean[] array, boolean x) { Arrays.fill(array, x); }
		void fill(int[][] array, int x) { for(int[] a : array) fill(a, x); }
		void fill(long[][] array, long x) { for(long[] a : array) fill(a, x); }
		void fill(double[][] array, double x) { for(double[] a : array) fill(a, x); }
		void fill(char[][] array, char x) { for(char[] a : array) fill(a, x); }
		void fill(boolean[][] array, boolean x) { for(boolean[] a : array) fill(a, x); }
		void fill(int[][][] array, int x) { for(int[][] a : array) fill(a, x); }
		void fill(long[][][] array, long x) { for(long[][] a : array) fill(a, x); }
		void fill(double[][][] array, double x) { for(double[][] a : array) fill(a, x); }
		void fill(char[][][] array, char x) { for(char[][] a : array) fill(a, x); }
		void fill(boolean[][][] array, boolean x) { for(boolean[][] a : array) fill(a, x); }


		int[] resize(int[] array, int m, int x) {
			int resized[] = new int[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}
		long[] resize(long[] array, int m, int x) {
			long resized[] = new long[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}
		double[] resize(double[] array, int m, int x) {
			double resized[] = new double[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}
		char[] resize(char[] array, int m, int x) {
			char resized[] = new char[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}
		boolean[] resize(boolean[] array, int m, int x) {
			boolean resized[] = new boolean[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}
		Object[] resize(Object[] array, int m, int x) {
			Object resized[] = new Object[m];
			for(int i = max(0, - x); i < array.length && i + x < m; i ++) resized[i + x] = array[i];
			return resized;
		}

		class PairLL implements Comparable<PairLL> {
			long a; long b;
			PairLL() { }
			PairLL(long a, long b) { this.a = a; this.b = b; }
			@Override public String toString() { return "("+a+", "+b+")"; }
			@Override public int hashCode() { return Objects.hash(a, b); }
			@Override
			public boolean equals(Object obj) {
				if(this == obj) return true;
				if(obj == null) return false;
				if(this.getClass() != obj.getClass()) return false;
				PairLL that = (PairLL) obj;
				if(this.a != that.a || this.b != that.b) return false;
				return true;
			}
			@Override
			public int compareTo(PairLL that) {
				int c = Long.compare(this.a, that.a);
				if(c == 0) c = Long.compare(this.b, that.b);
				return c;
			}
		}


		PairLL[] factor(long a) {
			List<PairLL> factorList = new ArrayList<>();
			for(long i = 2; i * i <= a; i ++) {
				if(a % i == 0) {
					long cnt = 0;
					while(a % i == 0) { a /= i; cnt ++; }
					factorList.add(new PairLL(i, cnt));
				}
			}
			if(a > 1) factorList.add(new PairLL(a, 1));
			PairLL factor[] = new PairLL[factorList.size()];
			for(int i = 0; i < factorList.size(); i ++) factor[i] = factorList.get(i);
			Arrays.sort(factor);
			return factor;
		}

public void solve() {
	int num = ni() + 1;
	long a[] = nl(num);
	long b[] = nl(num);
	long ans[] = convolution(a, b, (long)1e9 + 7);
	long sum = 0;
	for(int i = 0; i < num; i ++) {
		sum = mod(sum + ans[i], (long)1e9 + 7);
	}
	prtln(sum);
}

final long MOD1 = 754974721; // 2^24
final long MOD2 = 167772161; // 2^25
final long MOD3 = 469762049; // 2^26
final long M2M3 = MOD2 * MOD3;
final long M1M3 = MOD1 * MOD3;
final long M1M2 = MOD1 * MOD2;
final long M1M2M3 = MOD1 * MOD2 * MOD3;
final long M1INVM2 = 95869806; // inv(MOD1, MOD2);
final long INV1 = 190329765; // inv(MOD2 * MOD3, MOD1);
final long INV2 = 58587104; // inv(MOD1 * MOD3, MOD2);
final long INV3 = 187290749; // inv(MOD1 * MOD2, MOD3);
long[] convolution(long[] a, long[] b, long mod){
	final long M1M2MOD = mod(MOD1 * MOD2, mod);

	int n = a.length;
	int m = b.length;
	if(n == 0 || m == 0) return new long[0];

	long f1[] = new Convolution(MOD1).convolution(a, b);
	long f2[] = new Convolution(MOD2).convolution(a, b);
	long f3[] = new Convolution(MOD3).convolution(a, b);

	long f[] = new long[n + m - 1];
	for(int i = 0; i < f.length; i ++) {
		long v1 = mod((f2[i] - f1[i]) * M1INVM2, MOD2);
		long v2 = mod(mod(f3[i] - f1[i] - MOD1 * v1, MOD3) * INV3, MOD3);
		f[i] = mod(f1[i] + MOD1 * v1 + M1M2MOD * v2, mod);
	}
	return f;
}

long[] convolution(long[] a, long[] b) { // O((N+M)log(N+M))
	int n = a.length;
	int m = b.length;
	if(n == 0 || m == 0) return new long[0];

	long f1[] = new Convolution(MOD1).convolution(a, b);
	long f2[] = new Convolution(MOD2).convolution(a, b);
	long f3[] = new Convolution(MOD3).convolution(a, b);

	long f[] = new long[n + m - 1];
	for(int i = 0; i < n + m - 1; i ++) {
		long x = 0;
		x += (f1[i] * INV1) % MOD1 * M2M3;
		x += (f2[i] * INV2) % MOD2 * M1M3;
		x += (f3[i] * INV3) % MOD3 * M1M2;
		long diff = f1[i] - mod(x, MOD1);
		if(diff < 0) diff += MOD1;
		long offset[] = {0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
		x -= offset[(int)(diff % 5)];
		f[i] = x;
	}
	return f;
}

class Convolution { // M=mod
	long mod;
	long g;
	long sumE[];
	long sumIE[];
	int size = 30;
	Convolution(long mod) { // O(logM)
		this.mod = mod;
		g = primitiveRoot(mod);
		sumE = new long[size];
		sumIE = new long[size];
		prepareSum();
	}

	long primitiveRoot(long mod) { // O(1) or O(√M)
		if(mod == 2) return 1;
		if(mod == 167772161) return 3;
		if(mod == 469762049) return 3;
		if(mod == 754974721) return 11;
		if(mod == 998244353) return 3;

		PairLL factor[] = factor(mod - 1);
		outer: for(long g = 2; ; g ++) {
			for(PairLL p : factor) if(pow_m(g, (mod - 1) / p.a, mod) == 1) continue outer;
			return g;
		}
	}

	void prepareSum() { // O(logM)
		long[] es = new long[size];
		long[] ies = new long[size];
		int len = Long.numberOfTrailingZeros(mod - 1);
		long e = pow_m(g, (mod - 1) >> len, mod);
		long ie = pow_m(e, mod - 2, mod);
		for(int i = len - 2; i >= 0; i --) {
			es[i] = e;
			ies[i] = ie;
			e = mod(e * e, mod);
			ie = mod(ie * ie, mod);
		}
		long tmpE = 1;
		long tmpIE = 1;
		for(int i = 0; i < len - 2; i++) {
			sumE[i] = mod(es[i] * tmpE, mod);
			tmpE = mod(tmpE * ies[i], mod);
			sumIE[i] = mod(ies[i] * tmpIE, mod);
			tmpIE = mod(tmpIE * es[i], mod);
		}
	}

	void butterfly(long[] a) { // O(NlogN)
		int n = a.length;
		int h = 0;
		while((1L << h) < n) h ++;

		for(int ph = 1; ph <= h; ph ++) {
			int w = 1 << (ph - 1);
			int p = 1 << (h - ph);
			long tmp = 1;
			for(int s = 0; s < w; s ++) {
				int offset = s << (h - ph + 1);
				for(int i = 0; i < p; i ++) {
					long l = a[i + offset];
					long r = mod(a[i + offset + p] * tmp, mod);
					a[i + offset] = mod(l + r, mod);
					a[i + offset + p] = mod(l - r, mod);
				}
				int x = Integer.numberOfTrailingZeros(~s);
				tmp = mod(tmp * sumE[x], mod);
			}
		}
	}
	void butterflyInv(long[] a) { // O(NlogN)
		int n = a.length;
		int h = 0;
		while((1L << h) < n) h ++;

		for(int ph = h; ph >= 1; ph --) {
			int w = 1 << (ph - 1);
			int p = 1 << (h - ph);
			long tmp = 1;
			for(int s = 0; s < w; s ++) {
				int offset = s << (h - ph + 1);
				for (int i = 0; i < p; i++) {
					long l = a[i + offset];
					long r = a[i + offset + p];
					a[i + offset] = mod(l + r, mod);
					a[i + offset + p] = mod((l - r) * tmp, mod);
				}
				int x = Integer.numberOfTrailingZeros(~s);
				tmp = mod(tmp * sumIE[x], mod);
			}
		}
	}

	long[] convolution(long[] a, long[] b) { // O((N+M)log(N+M))
		int n = a.length;
		int m = b.length;
		if (n == 0 || m == 0) return new long[0];

		int len = 1;
		while(len < n + m - 1) len <<= 1;
		long g[] = resize(a, len, 0);
		long h[] = resize(b, len, 0);

		butterfly(g);
		butterfly(h);

		long f[] = new long[len];
		for(int i = 0; i < len; i ++) f[i] = mod(g[i] * h[i], mod);
		butterflyInv(f);
		f = resize(f, n + m - 1, 0);

		long invLen = inv(len, mod);
		for(int i = 0; i < f.length; i ++) f[i] = mod(f[i] * invLen, mod);
		return f;
	}
}
long mod(long x, long mod) { x %= mod; return x + (x < 0 ? mod : 0); } // O(1)
long pow_m(long x, long y, long mod) { // (logY)
	x = mod(x, mod);
	long ans = 1;
	for(; y > 0; y /= 2) {
		if(y % 2 != 0) ans = mod(ans * x, mod);
		x = mod(x * x, mod);
	}
	return ans;
}
long inv(long x, long mod) { return pow_m(x, mod - 2, mod); } // O(logM)

long garner(PairLL[] p, long mod){
	PairLL p2[] = new PairLL[p.length + 1];
	for(int i = 0; i < p.length; i ++) p2[i] = p[i];
	p = p2;
	p[p.length - 1] = new PairLL(mod, 0);

	long coffs[] = new long[p.length];
	fill(coffs, 1);
	long constants[] = new long[p.length];
	fill(constants, 0);
	for(int i = 0; i < p.length - 1; i ++) {
		long v = (p[i].b - constants[i]) * inv(coffs[i], p[i].a) % p[i].a;
		if(v < 0) v += p[i].a;

		for(int j = i + 1; j < p.length; j++) {
			constants[j] += coffs[j] * v;
			constants[j] %= p[j].a;
			coffs[j] *= p[i].a;
			coffs[j] %= p[j].a;
		}
	}

	return constants[p.length - 1];
}

	}
}