import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.BitSet;
import java.util.NoSuchElementException;


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

	public Main() {
		InputChecker ic = new InputChecker(System.in);
		java.io.PrintWriter out = new java.io.PrintWriter(System.out);
		solve(ic, out);
		out.flush();
	}

	static final int MAX = 3123456;

	static final long[] fac = new long[MAX];
	static final long[] ifac = new long[MAX];
	static final long[] inv = new long[MAX];
	static final long[] pw2 = new long[MAX];
	static final int MOD = 1_000_000_007;

	{
		fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = pw2[0] = 1;
		pw2[1] = 2;
		for (int i = 2; i < fac.length; ++i) {
			fac[i] = i * fac[i - 1] % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			ifac[i] = inv[i] * ifac[i - 1] % MOD;
			pw2[i] = 2 * pw2[i - 1] % MOD;
		}
	}

	static final long comb(int n, int k) {
		return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
	}

	public void solve(InputChecker ic, java.io.PrintWriter out) {
		int X = ic.nextInt();
		ic.nextChar(' ');
		int Y = ic.nextInt();
		ic.nextChar(' ');
		int Z = ic.nextInt();
		ic.readNewLine();
		ic.checkEOF();

		if (X == 0 && Y == 0 && Z == 0) {
			out.println(1);
			return;
		}

		int[] xxx = new int[] { X, Y, Z };
		Arrays.sort(xxx);
		X = xxx[2];
		Y = xxx[1];
		Z = xxx[0];
		int[] f = new int[Math.min(X + Y, Math.min(Y + Z, Z + X)) + 1];
		int[] g = new int[Math.min(X, Y) + 1];
		int[] h = new int[Z + 1];
		for (int i = 0; i < f.length; ++i) {
			f[i] = (int)(pw2[X + Y + Z - 1 - i] * (i % 2 == 0 ? 1 : MOD - 1) % MOD * fac[X + Y + Z - i] % MOD
					* ifac[X + Y - i] % MOD);
		}
		for (int i = 0; i < g.length; ++i) {
			g[Math.min(X, Y) - i] = (int)(fac[X + Y - i] * ifac[X - i] % MOD * ifac[Y - i] % MOD * ifac[i] % MOD);
		}
		for (int i = 0; i < h.length; ++i) {
			h[Z - i] = (int)(ifac[Z - i] * ifac[i] % MOD);
		}
		int[] fg = Convolution.convolution1_000_000_007(f, g);
		long ret = 0;
		for (int i = Math.max(0, Math.min(X, Y) + Z - h.length + 1); i < Math.min(fg.length,
				Math.min(X, Y) + Z + 1); ++i) {
			ret = (ret + (long)fg[i] * h[Math.min(X, Y) + Z - i]) % MOD;
		}
		out.println(ret);
	}

	public static int exponent10(int n, int e) {
		return n * pow(10, e);
	}

	public static long exponent10L(int n, int e) {
		return n * pow(10L, e);
	}

	public static int pow(int a, int b) {
		int ans = 1;
		for (int mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static long pow(long a, long b) {
		long ans = 1;
		for (long mul = a;b > 0;b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
		return ans;
	}

	public static class CharSet {
		private final BitSet set = new BitSet(256);

		public void add(char... c) {
			for (char i : c) set.set(i);
		}

		public void add(CharSet... s) {
			for (CharSet i : s) set.or(i.set);
		}

		public boolean contains(char... c) {
			for (char i : c) if (!set.get(i)) return false;
			return true;
	 	}

		public boolean contains(String s) {
			return contains(s.toCharArray());
	 	}

		private static final class Chars extends CharSet {
			public Chars(char... c) {
				super.add(c);
			}
			public Chars(CharSet... s) {
				super.add(s);
			}
			@Override
			public void add(char... c) {
				throw new UnsupportedOperationException();
			}
			@Override
			public void add(CharSet... s) {
				throw new UnsupportedOperationException();
			}
		}

		public static final CharSet NUMBER = new Chars('0','1','2','3','4','5','6','7','8','9');
		public static final CharSet LOWER = new Chars('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
		public static final CharSet UPPER = new Chars('A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z');
		public static final CharSet ALPHABET = new Chars(LOWER, UPPER);

	}
	public static class InputChecker {
		private InputStream in;
		private final byte[] buffer = new byte[1024];
		private final byte[] undo = new byte[1024];
		private int undoSize = 0;
		private int read = 0;
		private int length = 0;

		public InputChecker(InputStream in) {
			this.in = in;
		}

		public final void setInputStream(InputStream in) {
			this.in = in;
		}

		public final void setInputStream(File in) {
			try {
				this.in = new FileInputStream(in);
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		private boolean hasNextByte() {
			if (undoSize > 0) return true;
			if (read < length) return true;
			read = 0;
			try {
				length = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			return length > 0;
		}

		private byte readByte() {
			if (hasNextByte()) return undoSize > 0 ? undo[--undoSize] : buffer[read++];
			throw new NoSuchElementException();
		}

		private void undo(byte b) {
			undo[undoSize ++] = b;
		}

		private void undo(char c) {
			if ((c & 0xFF80) == 0) {
				undo((byte)c);
				return;
			}
			undo((byte)(c & 0x3F | 0x80));
			if ((c & 0xF800) == 0) {
				undo((byte)(c >> 6 & 0x1F | 0xC0));
			} else {
				undo((byte)(c >> 6 & 0x3F | 0x80));
				undo((byte)(c >> 12 | 0xE0));
			}
		}

		public final boolean hasNext() {
			return hasNextByte();
		}

		public final char nextChar() {
			byte b = readByte();
			if ((b & 0x80) == 0) return (char)b;
			if ((b & 0x20) == 0) return (char)((b & 0x1F) << 6 | readByte() & 0x3F);
			return (char)((b & 0xF) << 12 | (readByte() & 0x3F) << 6 | readByte() & 0x3F);
		}

		public final char nextChar(char estimate) {
			char c = nextChar();
			if (estimate == c) return estimate;
			undo(c);
			throw new AssertionError();
		}

		public final char nextChar(CharSet estimate) {
			char c = nextChar();
			if (estimate.contains(c)) return c;
			undo(c);
			throw new AssertionError();
		}

		public final void readNewLine() {
			char c = nextChar();
			if (c == '\r') {
				c = nextChar();
				if (c != '\n') undo(c);
				return;
			} else if (c == '\n') return;
			undo(c);
			throw new AssertionError();
		}

		public final void checkEOF() {
			if (hasNextByte()) throw new AssertionError();
		}

		public final String next(CharSet contains) {
			StringBuilder sb = new StringBuilder();
			try {
				do {
					char c = nextChar();
					if (!contains.contains(c)) {
						undo(c);
						return sb.toString();
					}
					sb.append(c);
				} while(true);
			} catch (NoSuchElementException e) {
				if (sb.length() <= 0) throw new AssertionError();
				return sb.toString();
			}
		}

		public final int nextInt() {
			byte b = readByte();
			int n = 0;
			if (b == '-') {
				if (!isNumber(b = readByte())) {
					undo(b);
					throw new NumberFormatException();
				}
				try {
					if (b == '0') {
						if (!isNumber(b = readByte())) {
							undo(b);
							return 0;
						}
						throw new NumberFormatException();
					}
					do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
					undo(b);
				} catch (NoSuchElementException e) {
				}
				return n;
			}
			if (!isNumber(b)) {
				undo(b);
				throw new NumberFormatException();
			}
			try {
				if (b == '0') {
					if (!isNumber(b = readByte())) {
						undo(b);
						return 0;
					}
					throw new NumberFormatException();
				}
				do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
				undo(b);
			} catch (NoSuchElementException e) {
			}
			return n;
		}

		public final int nextInt(int min, int max) {
			int n = nextInt();
			if (min <= n && n <= max) return n;
			throw new NumberFormatException();
		}

		private static boolean isNumber(byte c) {
			return '0' <= c && c <= '9';
		}

		public final long nextLong() {
			byte b = readByte();
			long n = 0;
			if (b == '-') {
				if (!isNumber(b = readByte())) {
					undo(b);
					throw new NumberFormatException();
				}
				try {
					if (b == '0') {
						if (!isNumber(b = readByte())) {
							undo(b);
							return 0;
						}
						throw new NumberFormatException();
					}
					do n = Math.addExact(Math.multiplyExact(n, 10), '0' - b); while(isNumber(b = readByte()));
					undo(b);
				} catch (NoSuchElementException e) {
				}
				return n;
			}
			if (!isNumber(b)) {
				undo(b);
				throw new NumberFormatException();
			}
			try {
				if (b == '0') {
					if (!isNumber(b = readByte())) {
						undo(b);
						return 0;
					}
					throw new NumberFormatException();
				}
				do n = Math.addExact(Math.multiplyExact(n, 10), b - '0'); while(isNumber(b = readByte()));
				undo(b);
			} catch (NoSuchElementException e) {
			}
			return n;
		}

		public final long nextLong(long min, long max) {
			long n = nextLong();
			if (min <= n && n <= max) return n;
			throw new NumberFormatException();
		}

		public final double nextDouble() {
			StringBuilder sb = new StringBuilder();
			byte b = readByte();
			if (b == '-') {
				sb.append(b);
				b = readByte();
			}
			if (b == '0') {
				sb.append(b);
				b = readByte();
			} else {
				while(isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			if (b == '.') {
				sb.append(b);
				b = readByte();
				while(isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			if (b == 'e' || b == 'E') {
				sb.append(b);
				b = readByte();
				if (b == '-' || b == '+') {
					sb.append(b);
					b = readByte();
				}
				while(isNumber(b)) {
					sb.append(b);
					b = readByte();
				}
			}
			undo(b);
			return Double.parseDouble(sb.toString());
		}
	}

	public static final class MathLib {

		public static class Barrett {
			private final int mod;
			private final long h, l;
			private final long MAX = 1L << 62;
			private final int MASK = (1 << 31) - 1;

			Barrett(final int mod) {
				this.mod = mod;
				final long t = MAX / mod;
				h = t >>> 31;
				l = t & MASK;
			}

			int reduce(final long x) {
				final long xh = x >>> 31, xl = x & MASK;
				long z = xl * l;
				z = xl * h + xh * l + (z >>> 31);
				z = xh * h + (z >>> 31);
				final int ret = (int) (x - z * mod);
				return ret >= mod ? ret - mod : ret;
			}
		}

		public static class BarrettSmall {
			private final int mod;
			final long t;

			BarrettSmall(final int mod) {
				this.mod = mod;
				t = (1L << 42) / mod;
			}

			int reduce(long x) {
				long q = x * t >> 42;
				x -= q * mod;
				return (int) (x >= mod ? x - mod : x);
			}
		}

		private static long safe_mod(long x, final long m) {
			x %= m;
			if (x < 0) x += m;
			return x;
		}

		private static long[] inv_gcd(long a, final long b) {
			a = safe_mod(a, b);
			if (a == 0) return new long[] { b, 0 };

			long s = b, t = a;
			long m0 = 0, m1 = 1;
			while (t > 0) {
				final long u = s / t;
				s -= t * u;
				m0 -= m1 * u;
				long tmp = s;
				s = t;
				t = tmp;
				tmp = m0;
				m0 = m1;
				m1 = tmp;
			}
			if (m0 < 0) m0 += b / s;
			return new long[] { s, m0 };
		}

		public static int pow(long n, long m, final int mod) {
			assert m >= 0 && mod >= 1;
			if (mod == 1) return 0;
			return pow(n, m, new Barrett(mod));
		}

		public static int pow(long n, long m, Barrett mod) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = mod.reduce(ans * num);
				m >>>= 1;
				num = mod.reduce(num * num);
			}
			return (int) ans;
		}

		public static int pow998_244_353(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 998_244_353;
				m >>>= 1;
				num = num * num % 998_244_353;
			}
			return (int) ans;
		}

		public static int pow754_974_721(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 754_974_721;
				m >>>= 1;
				num = num * num % 754_974_721;
			}
			return (int) ans;
		}

		public static int pow167_772_161(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 167_772_161;
				m >>>= 1;
				num = num * num % 167_772_161;
			}
			return (int) ans;
		}

		public static int pow469_762_049(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 469_762_049;
				m >>>= 1;
				num = num * num % 469_762_049;
			}
			return (int) ans;
		}

		public static int pow1_000_000_007(long n, long m) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = ans * num % 1_000_000_007;
				m >>>= 1;
				num = num * num % 1_000_000_007;
			}
			return (int) ans;
		}

		public static int pow(long n, long m, BarrettSmall mod) {
			assert m >= 0;
			long ans = 1, num = n;
			while (m != 0) {
				if ((m & 1) != 0) ans = mod.reduce(ans * num);
				m >>>= 1;
				num = mod.reduce(num * num);
			}
			return (int) ans;
		}

		public static long[] crt(final long[] r, final long[] m) {
			assert r.length == m.length;
			final int n = r.length;

			long r0 = 0, m0 = 1;
			for (int i = 0; i < n; i++) {
				assert 1 <= m[i];
				long r1 = safe_mod(r[i], m[i]), m1 = m[i];
				if (m0 < m1) {
					long tmp = r0;
					r0 = r1;
					r1 = tmp;
					tmp = m0;
					m0 = m1;
					m1 = tmp;
				}
				if (m0 % m1 == 0) {
					if (r0 % m1 != r1) return new long[] { 0, 0 };
					continue;
				}

				final long[] ig = inv_gcd(m0, m1);
				final long g = ig[0], im = ig[1];

				final long u1 = m1 / g;
				if ((r1 - r0) % g != 0) return new long[] { 0, 0 };

				final long x = (r1 - r0) / g % u1 * im % u1;

				r0 += x * m0;
				m0 *= u1;
				if (r0 < 0) r0 += m0;
				// System.err.printf("%d %d\n", r0, m0);
			}
			return new long[] { r0, m0 };
		}

		public static long floor_sum(final long n, final long m, long a, long b) {
			long ans = 0;
			if (a >= m) {
				ans += (n - 1) * n * (a / m) / 2;
				a %= m;
			}
			if (b >= m) {
				ans += n * (b / m);
				b %= m;
			}

			final long y_max = (a * n + b) / m;
			final long x_max = y_max * m - b;
			if (y_max == 0) return ans;
			ans += (n - (x_max + a - 1) / a) * y_max;
			ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
			return ans;
		}
	}

	/**
	 * Convolution.
	 *
	 * @verified https://atcoder.jp/contests/practice2/tasks/practice2_f
	 * @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007
	 */
	public static final class Convolution {
		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		private static void fft(double[] a, double[] b, boolean invert) {
			int count = a.length;
			for (int i = 1, j = 0; i < count; i++) {
				int bit = count >> 1;
				for (; j >= bit; bit >>= 1) {
					j -= bit;
				}
				j += bit;
				if (i < j) {
					double temp = a[i];
					a[i] = a[j];
					a[j] = temp;
					temp = b[i];
					b[i] = b[j];
					b[j] = temp;
				}
			}
			for (int len = 2; len <= count; len <<= 1) {
				int halfLen = len >> 1;
				double angle = 2 * Math.PI / len;
				if (invert) {
					angle = -angle;
				}
				double wLenA = Math.cos(angle);
				double wLenB = Math.sin(angle);
				for (int i = 0; i < count; i += len) {
					double wA = 1;
					double wB = 0;
					for (int j = 0; j < halfLen; j++) {
						double uA = a[i + j];
						double uB = b[i + j];
						double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
						double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
						a[i + j] = uA + vA;
						b[i + j] = uB + vB;
						a[i + j + halfLen] = uA - vA;
						b[i + j + halfLen] = uB - vB;
						double nextWA = wA * wLenA - wB * wLenB;
						wB = wA * wLenB + wB * wLenA;
						wA = nextWA;
					}
				}
			}
			if (invert) {
				for (int i = 0; i < count; i++) {
					a[i] /= count;
					b[i] /= count;
				}
			}
		}

		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		public static long[] convolution(long[] a, long[] b) {
			int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
			resultSize = Math.max(resultSize, 1);
			double[] aReal = new double[resultSize];
			double[] aImaginary = new double[resultSize];
			double[] bReal = new double[resultSize];
			double[] bImaginary = new double[resultSize];
			for (int i = 0; i < a.length; i++) aReal[i] = a[i];
			for (int i = 0; i < b.length; i++) bReal[i] = b[i];

			fft(aReal, aImaginary, false);
			if (a == b) {
				System.arraycopy(aReal, 0, bReal, 0, aReal.length);
				System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
			} else {
				fft(bReal, bImaginary, false);
			}
			for (int i = 0; i < resultSize; i++) {
				double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
				aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
				aReal[i] = real;
			}
			fft(aReal, aImaginary, true);
			long[] result = new long[a.length + b.length - 1];
			for (int i = 0; i < result.length; i++) result[i] = Math.round(aReal[i]);
			return result;
		}

		/**
		 * writer: amotama 勝手に借りてます、問題あったらごめんね
		 */
		public static int[] convolution(int[] a, int[] b) {
			int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
			resultSize = Math.max(resultSize, 1);
			double[] aReal = new double[resultSize];
			double[] aImaginary = new double[resultSize];
			double[] bReal = new double[resultSize];
			double[] bImaginary = new double[resultSize];
			for (int i = 0; i < a.length; i++) aReal[i] = a[i];
			for (int i = 0; i < b.length; i++) bReal[i] = b[i];
			fft(aReal, aImaginary, false);
			if (a == b) {
				System.arraycopy(aReal, 0, bReal, 0, aReal.length);
				System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
			} else {
				fft(bReal, bImaginary, false);
			}
			for (int i = 0; i < resultSize; i++) {
				double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
				aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
				aReal[i] = real;
			}
			fft(aReal, aImaginary, true);
			int[] result = new int[a.length + b.length - 1];
			for (int i = 0; i < result.length; i++) result[i] = (int) Math.round(aReal[i]);
			return result;
		}

		/**
		 * Find a primitive root.
		 *
		 * @param m A prime number.
		 * @return Primitive root.
		 */
		private static int primitiveRoot(final int m) {
			if (m == 2) return 1;
			if (m == 167772161) return 3;
			if (m == 469762049) return 3;
			if (m == 754974721) return 11;
			if (m == 998244353) return 3;

			final int[] divs = new int[20];
			divs[0] = 2;
			int cnt = 1;
			int x = (m - 1) / 2;
			while (x % 2 == 0) x /= 2;
			for (int i = 3; (long) i * i <= x; i += 2) {
				if (x % i == 0) {
					divs[cnt++] = i;
					while (x % i == 0) {
						x /= i;
					}
				}
			}
			if (x > 1) {
				divs[cnt++] = x;
			}
			for (int g = 2;; g++) {
				boolean ok = true;
				for (int i = 0; i < cnt; i++) {
					if (MathLib.pow(g, (m - 1) / divs[i], m) == 1) {
						ok = false;
						break;
					}
				}
				if (ok) return g;
			}
		}

		/**
		 * Ceil of power 2.
		 *
		 * @param n Value.
		 * @return Ceil of power 2.
		 */
		private static int ceilPow2(final int n) {
			int x = 0;
			while (1L << x < n) x++;
			return x;
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static long garner(final long[] c, final int[] mods) {
			final int n = c.length + 1;
			final long[] cnst = new long[n];
			final long[] coef = new long[n];
			java.util.Arrays.fill(coef, 1);
			for (int i = 0; i < n - 1; i++) {
				final int m1 = mods[i];
				long v = (c[i] - cnst[i] + m1) % m1;
				v = v * MathLib.pow(coef[i], m1 - 2, m1) % m1;

				for (int j = i + 1; j < n; j++) {
					final long m2 = mods[j];
					cnst[j] = (cnst[j] + coef[j] * v) % m2;
					coef[j] = coef[j] * m1 % m2;
				}
			}
			return cnst[n - 1];
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static int garner(int c0, int c1, int c2, final MathLib.Barrett[] mods) {
			final long[] cnst = new long[4];
			final long[] coef = new long[4];
			java.util.Arrays.fill(coef, 1);
			MathLib.Barrett m1 = mods[0];
			long v = m1.reduce(c0 - cnst[0] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[0], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[1];
				cnst[1] = m2.reduce(cnst[1] + coef[1] * v);
				coef[1] = m2.reduce(coef[1] * m1.mod);
				m2 = mods[2];
				cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
				coef[2] = m2.reduce(coef[2] * m1.mod);
				m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			m1 = mods[1];
			v = m1.reduce(c1 - cnst[1] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[1], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[2];
				cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
				coef[2] = m2.reduce(coef[2] * m1.mod);
				m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			m1 = mods[2];
			v = m1.reduce(c2 - cnst[2] + m1.mod);
			v = m1.reduce(v * MathLib.pow(coef[2], m1.mod - 2, m1));
			{
				MathLib.Barrett m2 = mods[3];
				cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
				coef[3] = m2.reduce(coef[3] * m1.mod);
			}
			return (int) cnst[3];
		}

		/**
		 * Garner's algorithm.
		 *
		 * @param c    Mod convolution results.
		 * @param mods Mods.
		 * @return Result.
		 */
		private static int garner1_000_000_007(int c0, int c1, int c2) {
			final long[] cnst = new long[4];
			final long[] coef = new long[4];
			java.util.Arrays.fill(coef, 1);
			long v = (c0 - cnst[0] + 754_974_721) % 754_974_721;
			v = v * MathLib.pow754_974_721(coef[0], 754_974_721 - 2) % 754_974_721;
			{
				cnst[1] = (cnst[1] + coef[1] * v) % 167_772_161;
				coef[1] = coef[1] * 754_974_721 % 167_772_161;
				cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
				coef[2] = coef[2] * 754_974_721 % 469_762_049;
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 754_974_721 % 1_000_000_007;
			}
			v = (c1 - cnst[1] + 167_772_161) % 167_772_161;
			v = v * MathLib.pow167_772_161(coef[1], 167_772_161 - 2) % 167_772_161;
			{
				cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
				coef[2] = coef[2] * 167_772_161 % 469_762_049;
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 167_772_161 % 1_000_000_007;
			}
			v = (c2 - cnst[2] + 469_762_049) % 469_762_049;
			v = v * MathLib.pow469_762_049(coef[2], 469_762_049 - 2) % 469_762_049;
			{
				cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
				coef[3] = coef[3] * 469_762_049 % 1_000_000_007;
			}
			return (int) cnst[3];
		}

		/**
		 * Pre-calculation for NTT.
		 *
		 * @param mod NTT Prime.
		 * @param g   Primitive root of mod.
		 * @return Pre-calculation table.
		 */
		private static long[] sumE(final int mod, final int g) {
			final long[] sum_e = new long[30];
			final long[] es = new long[30];
			final long[] ies = new long[30];
			final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
			long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
			long ie = MathLib.pow(e, mod - 2, mod);
			for (int i = cnt2; i >= 2; i--) {
				es[i - 2] = e;
				ies[i - 2] = ie;
				e = e * e % mod;
				ie = ie * ie % mod;
			}
			long now = 1;
			for (int i = 0; i < cnt2 - 2; i++) {
				sum_e[i] = es[i] * now % mod;
				now = now * ies[i] % mod;
			}
			return sum_e;
		}

		/**
		 * Pre-calculation for inverse NTT.
		 *
		 * @param mod Mod.
		 * @param g   Primitive root of mod.
		 * @return Pre-calculation table.
		 */
		private static long[] sumIE(final int mod, final int g) {
			final long[] sum_ie = new long[30];
			final long[] es = new long[30];
			final long[] ies = new long[30];

			final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
			long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
			long ie = MathLib.pow(e, mod - 2, mod);
			for (int i = cnt2; i >= 2; i--) {
				es[i - 2] = e;
				ies[i - 2] = ie;
				e = e * e % mod;
				ie = ie * ie % mod;
			}
			long now = 1;
			for (int i = 0; i < cnt2 - 2; i++) {
				sum_ie[i] = ies[i] * now % mod;
				now = now * es[i] % mod;
			}
			return sum_ie;
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 * @param mod   NTT Prime.
		 */
		private static void butterflyInv(final long[] a, final long[] sumIE, final int mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly(final long[] a, final long[] sumE, final int mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT used mod 998_244_353.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv998_244_353(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT used mod 754_974_721.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv754_974_721(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT used mod 167_772_161.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv167_772_161(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT used mod 469_762_049.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 */
		private static void butterflyInv469_762_049(final int[] a, final int[] sumIE) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT.
		 *
		 * @param a     Target array.
		 * @param sumIE Pre-calculation table.
		 * @param mod   NTT Prime.
		 */
		private static void butterflyInv(final int[] a, final int[] sumIE, final MathLib.Barrett mod) {
			final int n = a.length;
			final int h = ceilPow2(n);

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

		/**
		 * Inverse NTT used mod 998_244_353.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly998_244_353(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(998_244_353 - 2) * 998_244_353;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 998_244_353);
						a[i + offset + p] = (int)((l - r + ADD) % 998_244_353);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 998_244_353;
				}
			}
		}

		/**
		 * Inverse NTT used mod 754_974_721.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly754_974_721(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(754_974_721 - 2) * 754_974_721;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 754_974_721);
						a[i + offset + p] = (int)((l - r + ADD) % 754_974_721);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 754_974_721;
				}
			}
		}

		/**
		 * Inverse NTT used mod 167_772_161.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly167_772_161(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(167_772_161 - 2) * 167_772_161;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 167_772_161);
						a[i + offset + p] = (int)((l - r + ADD) % 167_772_161);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 167_772_161;
				}
			}
		}

		/**
		 * Inverse NTT used mod 469_762_049.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly469_762_049(final int[] a, final int[] sumE) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(469_762_049 - 2) * 469_762_049;

			for (int ph = 1; ph <= h; ph++) {
				final int w = 1 << ph - 1, p = 1 << h - ph;
				long now = 1;
				for (int s = 0; s < w; s++) {
					final int offset = s << h - ph + 1;
					for (int i = 0; i < p; i++) {
						final long l = a[i + offset];
						final long r = a[i + offset + p] * now;
						a[i + offset] = (int)((l + r) % 469_762_049);
						a[i + offset + p] = (int)((l - r + ADD) % 469_762_049);
					}
					final int x = Integer.numberOfTrailingZeros(~s);
					now = now * sumE[x] % 469_762_049;
				}
			}
		}

		/**
		 * Inverse NTT.
		 *
		 * @param a    Target array.
		 * @param sumE Pre-calculation table.
		 * @param mod  NTT Prime.
		 */
		private static void butterfly(final int[] a, final int[] sumE, final MathLib.Barrett mod) {
			final int n = a.length;
			final int h = ceilPow2(n);
			final long ADD = (long)(mod.mod - 2) * mod.mod;

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

		/**
		 * Convolution used mod 998_244_353.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution998_244_353(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(998_244_353);
			final int[] sume;
			{
				long[] s = sumE(998_244_353, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(998_244_353, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly998_244_353(a, sume);
			butterfly998_244_353(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 998_244_353);
			butterflyInv998_244_353(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow998_244_353(z, 998_244_353 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 998_244_353);
			return a;
		}

		/**
		 * Convolution used mod 754_974_721.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution754_974_721(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(754_974_721);
			final int[] sume;
			{
				long[] s = sumE(754_974_721, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(754_974_721, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly754_974_721(a, sume);
			butterfly754_974_721(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 754_974_721);
			butterflyInv754_974_721(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow754_974_721(z, 754_974_721 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 754_974_721);
			return a;
		}

		/**
		 * Convolution used mod 167_772_161.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution167_772_161(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(167_772_161);
			final int[] sume;
			{
				long[] s = sumE(167_772_161, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(167_772_161, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly167_772_161(a, sume);
			butterfly167_772_161(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 167_772_161);
			butterflyInv167_772_161(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow167_772_161(z, 167_772_161 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 167_772_161);
			return a;
		}

		/**
		 * Convolution used mod 469_762_049.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution469_762_049(int[] a, int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(469_762_049);
			final int[] sume;
			{
				long[] s = sumE(469_762_049, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(469_762_049, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly469_762_049(a, sume);
			butterfly469_762_049(b, sume);
			for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 469_762_049);
			butterflyInv469_762_049(a, sumie);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow469_762_049(z, 469_762_049 - 2);
			for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 469_762_049);
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod NTT Prime.
		 * @return Answer.
		 */
		public static int[] convolution(int[] a, int[] b, final int mod) {
			MathLib.Barrett barrett = new MathLib.Barrett(mod);
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final int[] na = new int[z];
				final int[] nb = new int[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(mod);
			final int[] sume;
			{
				long[] s = sumE(mod, g);
				sume = new int[s.length];
				for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
			}
			final int[] sumie;
			{
				long[] s = sumIE(mod, g);
				sumie = new int[s.length];
				for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
			}

			butterfly(a, sume, barrett);
			butterfly(b, sume, barrett);
			for (int i = 0; i < z; i++) a[i] = barrett.reduce((long) a[i] * b[i]);
			butterflyInv(a, sumie, barrett);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow(z, mod - 2, mod);
			for (int i = 0; i < n + m - 1; i++) a[i] = barrett.reduce(a[i] * iz);
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod NTT Prime.
		 * @return Answer.
		 */
		public static long[] convolution(long[] a, long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new long[0];

			final int z = 1 << ceilPow2(n + m - 1);
			{
				final long[] na = new long[z];
				final long[] nb = new long[z];
				System.arraycopy(a, 0, na, 0, n);
				System.arraycopy(b, 0, nb, 0, m);
				a = na;
				b = nb;
			}

			final int g = primitiveRoot(mod);
			final long[] sume = sumE(mod, g);
			final long[] sumie = sumIE(mod, g);

			butterfly(a, sume, mod);
			butterfly(b, sume, mod);
			for (int i = 0; i < z; i++) {
				a[i] = a[i] * b[i] % mod;
			}
			butterflyInv(a, sumie, mod);
			a = java.util.Arrays.copyOf(a, n + m - 1);

			final long iz = MathLib.pow(z, mod - 2, mod);
			for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
			return a;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static long[] convolutionLL(final long[] a, final long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new long[0];

			final int mod1 = 754_974_721;
			final int mod2 = 167_772_161;
			final int mod3 = 469_762_049;

			final long[] c1 = convolution(a, b, mod1);
			final long[] c2 = convolution(a, b, mod2);
			final long[] c3 = convolution(a, b, mod3);

			final int retSize = c1.length;
			final long[] ret = new long[retSize];
			final int[] mods = { mod1, mod2, mod3, mod };
			for (int i = 0; i < retSize; ++i) {
				ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);
			}
			return ret;
		}

		/**
		 * Convolution.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static int[] convolutionLL(final int[] a, final int[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int mod1 = 754_974_721;
			final int mod2 = 167_772_161;
			final int mod3 = 469_762_049;

			final int[] c1 = convolution754_974_721(a, b);
			final int[] c2 = convolution167_772_161(a, b);
			final int[] c3 = convolution469_762_049(a, b);

			final int retSize = c1.length;
			final int[] ret = new int[retSize];
			final MathLib.Barrett[] mods = { new MathLib.Barrett(mod1), new MathLib.Barrett(mod2),
					new MathLib.Barrett(mod3), new MathLib.Barrett(mod) };
			for (int i = 0; i < retSize; ++i) ret[i] = garner(c1[i], c2[i], c3[i], mods);
			return ret;
		}

		/**
		 * Convolution used mod 1_000_000_007.
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @return Answer.
		 */
		public static int[] convolution1_000_000_007(final int[] a, final int[] b) {
			final int n = a.length;
			final int m = b.length;
			if (n == 0 || m == 0) return new int[0];

			final int[] c1 = convolution754_974_721(a, b);
			final int[] c2 = convolution167_772_161(a, b);
			final int[] c3 = convolution469_762_049(a, b);

			final int retSize = c1.length;
			final int[] ret = new int[retSize];
			for (int i = 0; i < retSize; ++i) ret[i] = garner1_000_000_007(c1[i], c2[i], c3[i]);
			return ret;
		}

		/**
		 * Convolution. need: length < 2000
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Any mod.
		 * @return Answer.
		 */
		public static int[] convolutionLL2(final int[] a, final int[] b, final int mod) {
			if (Math.max(a.length, b.length) < 4000) {
				long[] la = new long[a.length], ha = new long[a.length], ma = new long[a.length], lb = new long[b.length],
						hb = new long[b.length], mb = new long[b.length];
				MathLib.Barrett barrett = new MathLib.Barrett(mod);
				for (int i = 0; i < a.length; ++i) {
					ha[i] = a[i] >> 15;
					la[i] = a[i] & 0x7FFF;
					ma[i] = la[i] + ha[i];
				}
				for (int i = 0; i < b.length; ++i) {
					hb[i] = b[i] >> 15;
					lb[i] = b[i] & 0x7FFF;
					mb[i] = lb[i] + hb[i];
				}
				long[] l = convolution(la, lb), h = convolution(ha, hb), m = convolution(ma, mb);
				int[] ret = new int[m.length];
				for (int i = 0; i < m.length; ++i) {
					h[i] = barrett.reduce(h[i]);
					m[i] = barrett.reduce(m[i] - l[i] - h[i] + (long)m.length * mod);
					ret[i] = barrett.reduce((h[i] << 30) + (m[i] << 15) + l[i]);
				}
				return ret;
			}
			return convolutionLL(a, b, mod);
		}

		/**
		 * Naive convolution. (Complexity is O(N^2)!!)
		 *
		 * @param a   Target array 1.
		 * @param b   Target array 2.
		 * @param mod Mod.
		 * @return Answer.
		 */
		public static long[] convolutionNaive(final long[] a, final long[] b, final int mod) {
			final int n = a.length;
			final int m = b.length;
			final int k = n + m - 1;
			final long[] ret = new long[k];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					ret[i + j] += a[i] * b[j] % mod;
					ret[i + j] %= mod;
				}
			}
			return ret;
		}
	}
}