import java.awt.Dimension;
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.function.*;
public class Main{
	static SimpleScanner sc=new SimpleScanner(System.in);
	static SimpleWriter out=new SimpleWriter(System.out);
	public static void main(String[]args){
		int H=sc.nextInt();
		int W=sc.nextInt();
		var A=new Matrix(H,W);
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				A.set(i,j,sc.nextInt());
		var B=new Matrix(W,H);
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				B.set(j,i,sc.nextInt());
		var C=A.modMultiply(B,998244353);
		for(int i=0;i<H;i++)
			C.set(i,i,(C.get(i,i)+1)%998244353);
		out.println(C.determinant()-1);
		out.close();
	}
}
/*////////////////////////////////////////////////////////////////////////////////////////////
                                        * My Library *

                                        @author  viral
*/////////////////////////////////////////////////////////////////////////////////////////////
class Factorial{
	long[]fact,inFact;
	long mod;
	Factorial(int N,long mod){fact=new long[N+1];fact[0]=fact[1]=1;for(int i=2;i<=N;++i)fact[i]=fact[i-1]*i%mod;inFact=new long[N+1];inFact[N]=MathFunction.modPow(fact[N],mod-2,mod);for(int i=N;i>0;--i)inFact[i-1]=inFact[i]*i%mod;inFact[0]=1;this.mod=mod;}
	long getFact(int num){return fact[num];}
	long getInFact(int num){return inFact[num];}
	long getInverse(int num){return fact[num-1]*inFact[num]%mod;}
	long getCombi(int a,int b){if(a<b||a<0||b<0)return 0;return (fact[a]*inFact[a-b]%mod)*inFact[b]%mod;}
}
class ArrayFunction{
	static void countSort(int[] array,int maximumLimit){
		countSort(array,0,array.length,maximumLimit);
	}
	static void countSort(int[] array,int l,int r,int maximumLimit){
		int[] list=new int[maximumLimit+1];
		for(int i=l;i<r;++i){
			++list[array[i]];
		}
		int temp=l;
		for(int i=0;i<list.length;++i){
			while(list[i]-->0){
				array[temp++]=i;
			}
		}
	}
	static void insertSort(int[] array){
		insertSort(array,0,array.length);
	}
	static void insertSort(int[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			int num=array[j];
			while(l<j&&array[j-1]>num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static void insertSort(long[] array){
		insertSort(array,0,array.length);
	}
	static void insertSort(long[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			long num=array[j];
			while(l<j&&array[j-1]>num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static void insertSort(char[] array){
		insertSort(array,0,array.length);
	}
	static void insertSort(char[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			char num=array[j];
			while(l<j&&array[j-1]>num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static <E extends Comparable<E>> void insertSort(E[] array){
		insertSort(array,0,array.length);
	}
	static <E extends Comparable<E>> void insertSort(E[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			E num=array[j];
			while(l<j&&array[j-1].compareTo(num)>0){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static void reverseInsertSort(int[] array){
		reverseInsertSort(array,0,array.length);
	}
	static void reverseInsertSort(int[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			int num=array[j];
			while(l<j&&array[j-1]<num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static void reverseInsertSort(long[] array){
		reverseInsertSort(array,0,array.length);
	}
	static void reverseInsertSort(long[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			long num=array[j];
			while(l<j&&array[j-1]<num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static void reverseInsertSort(char[] array){
		reverseInsertSort(array,0,array.length);
	}
	static void reverseInsertSort(char[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			char num=array[j];
			while(l<j&&array[j-1]<num){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static <E extends Comparable<E>> void reverseInsertSort(E[] array){
		reverseInsertSort(array,0,array.length);
	}
	static <E extends Comparable<E>> void reverseInsertSort(E[] array,int l,int r){
		for(int i=l+1;i<r;i++){
			int j=i;
			E num=array[j];
			while(l<j&&array[j-1].compareTo(num)<0){
				array[j]=array[j-1];
				--j;
			}
			array[j]=num;
		}
	}
	static int[][] rotateR(int[][] array){
		int[][] ans=new int[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static long[][] rotateR(long[][] array){
		long[][] ans=new long[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static char[][] rotateR(char[][] array){
		char[][] ans=new char[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static double[][] rotateR(double[][] array){
		double[][] ans=new double[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static boolean[][] rotateR(boolean[][] array){
		boolean[][] ans=new boolean[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static <E> E[][] rotateR(E[][] array,E[][] ans){
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[ans[i].length-j-1][i];
			}
		}
		return ans;
	}
	static int[][] rotateL(int[][] array){
		int[][] ans=new int[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			int index=i;
			Arrays.setAll(ans[i],k->array[k][ans.length-index-1]);
		}
		return ans;
	}
	static long[][] rotateL(long[][] array){
		long[][] ans=new long[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			int index=i;
			Arrays.setAll(ans[i],k->array[k][ans.length-index-1]);
		}
		return ans;
	}
	static char[][] rotateL(char[][] array){
		char[][] ans=new char[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[j][ans.length-i-1];
			}
		}
		return ans;
	}
	static double[][] rotateL(double[][] array){
		double[][] ans=new double[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[j][ans.length-i-1];
			}
		}
		return ans;
	}
	static boolean[][] rotateL(boolean[][] array){
		boolean[][] ans=new boolean[array[0].length][array.length];
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[j][ans.length-i-1];
			}
		}
		return ans;
	}
	static <E> E[][] rotateL(E[][] array,E[][] ans){
		for(int i=0;i<ans.length;++i){
			for(int j=0;j<ans[i].length;++j){
				ans[i][j]=array[j][ans.length-i-1];
			}
		}
		return ans;
	}
	static int lis(int[] array){
		return lis(array,false);
	}
	static int lis(int[][] arrays,int p){
		return lis(arrays,p,false);
	}
	static int lis(long[] array){
		return lis(array,false);
	}
	static int lis(long[][] arrays,int p){
		return lis(arrays,p,false);
	}
	static int lis(int[] array,boolean include){
		int[] list=new int[array.length];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int num: array){
			int index=include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
			list[index]=Math.min(list[index],num);
		}
		int answer=Searcher.underSearch(list,Integer.MAX_VALUE);
		return answer+1;
	}
	static int lis(int[][] arrays,int p,boolean include){
		int[] list=new int[arrays.length];
		Arrays.fill(list,Integer.MAX_VALUE);
		for(int[] array: arrays){
			int index=include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
			list[index]=Math.min(list[index],array[p]);
		}
		int answer=Searcher.underSearch(list,Integer.MAX_VALUE);
		return answer+1;
	}
	static int lis(long[] array,boolean include){
		long[] list=new long[array.length];
		Arrays.fill(list,Long.MAX_VALUE);
		for(long num: array){
			int index=include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
			list[index]=Math.min(list[index],num);
		}
		int answer=Searcher.underSearch(list,Long.MAX_VALUE);
		return answer+1;
	}
	static int lis(long[][] arrays,int p,boolean include){
		long[] list=new long[arrays.length];
		Arrays.fill(list,Long.MAX_VALUE);
		for(long[] array: arrays){
			int index=include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
			list[index]=Math.min(list[index],array[p]);
		}
		int answer=Searcher.underSearch(list,Long.MAX_VALUE);
		return answer+1;
	}
	static int[][] topologicalSort(ArrayList<ArrayList<Integer>> route){
		int[] count=new int[route.size()];
		int pathCount=0;
		for(ArrayList<Integer> path: route){
			for(int point: path){
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq=new ArrayDeque<>();
		for(int i=1;i<count.length;++i){
			if(count[i]==0){
				deq.add(i);
			}
		}
		int[][] ans=new int[pathCount][2];
		int index=0;
		while(deq.size()>0){
			int nowP=deq.pollFirst();
			for(int nextP: route.get(nowP)){
				ans[index][0]=nowP;
				ans[index++][1]=nextP;
				if(--count[nextP]==0){
					deq.add(nextP);
				}
			}
		}
		return ans;
	}
	static int[][] topologicalSort(int[][] route){
		int[] count=new int[route.length];
		int pathCount=0;
		for(int[] path: route){
			for(int point: path){
				++pathCount;
				++count[point];
			}
		}
		ArrayDeque<Integer> deq=new ArrayDeque<>();
		for(int i=1;i<count.length;++i){
			if(count[i]==0){
				deq.add(i);
			}
		}
		int[][] ans=new int[pathCount][2];
		int index=0;
		while(deq.size()>0){
			int nowP=deq.pollFirst();
			for(int nextP: route[nowP]){
				ans[index][0]=nowP;
				ans[index++][1]=nextP;
				if(--count[nextP]==0){
					deq.add(nextP);
				}
			}
		}
		return ans;
	}
	static void swap(int[] array,int a,int b){
		int temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static void swap(long[] array,int a,int b){
		long temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static void swap(double[] array,int a,int b){
		double temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static void swap(char[] array,int a,int b){
		char temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static void swap(boolean[] array,int a,int b){
		boolean temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static <E> void swap(E[] array,int a,int b){
		E temp=array[a];
		array[a]=array[b];
		array[b]=temp;
	}
	static void swap(int[][] array,int a,int b,int c,int d){
		int temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static void swap(long[][] array,int a,int b,int c,int d){
		long temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static void swap(double[][] array,int a,int b,int c,int d){
		double temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static void swap(char[][] array,int a,int b,int c,int d){
		char temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static void swap(boolean[][] array,int a,int b,int c,int d){
		boolean temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static <E> void swap(E[][] array,int a,int b,int c,int d){
		E temp=array[a][b];
		array[a][b]=array[c][d];
		array[c][d]=temp;
	}
	static boolean nextPermutation(int[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]<array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		int min=Integer.MAX_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		insertSort(array,index1+1,array.length);
		return true;
	}
	static boolean nextPermutation(long[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]<array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		long min=Long.MAX_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		insertSort(array,index1+1,array.length);
		return true;
	}
	static boolean nextPermutation(char[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]<array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		int min=Integer.MAX_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
				min=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		insertSort(array,index1+1,array.length);
		return true;
	}
	static <E extends Comparable<E>> boolean nextPermutation(E[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1].compareTo(array[i])<0){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		E min=MathFunction.max(array);
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckSubClose(array[i],array[index1],min)){
				min=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		insertSort(array,index1+1,array.length);
		return true;
	}
	static boolean previousPermutation(int[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]>array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		int max=Integer.MIN_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
				max=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		reverseInsertSort(array,index1+1,array.length);
		return true;
	}
	static boolean previousPermutation(long[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]>array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		long max=Long.MIN_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
				max=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		reverseInsertSort(array,index1+1,array.length);
		return true;
	}
	static boolean previousPermutation(char[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1]>array[i]){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		int max=Integer.MIN_VALUE;
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
				max=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		reverseInsertSort(array,index1+1,array.length);
		return true;
	}
	static <E extends Comparable<E>> boolean previousPermutation(E[] array){
		int index1=0;
		for(int i=1;i<array.length;++i){
			if(array[i-1].compareTo(array[i])>0){
				index1=i;
			}
		}
		if(--index1<0){
			return false;
		}
		int index2=0;
		E max=MathFunction.min(array);
		for(int i=index1+1;i<array.length;++i){
			if(MathFunction.rangeCheck(array[i],max,array[index1])){
				max=array[i];
				index2=i;
			}
		}
		swap(array,index1,index2);
		reverseRange(array,index1+1,array.length);
		reverseInsertSort(array,index1+1,array.length);
		return true;
	}
	static int[] reBuild(int[] array,IntUnaryOperator func){
		int[] ans=new int[array.length];
		for(int i=0;i<array.length;++i){
			ans[i]=func.applyAsInt(array[i]);
		}
		return ans;
	}
	static int[] reBuild(int[] array,IntBinaryOperator func){
		int[] ans=new int[array.length];
		for(int i=0;i<array.length;++i){
			ans[i]=func.applyAsInt(i,array[i]);
		}
		return ans;
	}
	static long[] reBuild(long[] array,LongUnaryOperator func){
		long[] ans=new long[array.length];
		for(int i=0;i<array.length;++i){
			ans[i]=func.applyAsLong(array[i]);
		}
		return ans;
	}
	static long[] reBuild(long[] array,LongBinaryOperator func){
		long[] ans=new long[array.length];
		for(int i=0;i<array.length;++i){
			ans[i]=func.applyAsLong(i,array[i]);
		}
		return ans;
	}
	static void computeByArray(int[] array,IntConsumer func){
		for(int num: array){
			func.accept(num);
		}
	}
	static void reverseRange(int[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static void reverseRange(long[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static void reverseRange(double[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static void reverseRange(char[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static void reverseRange(boolean[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static <E> void reverseRange(E[] array,int l,int r){
		while(l<r)
			swap(array,l++,--r);
	}
	static Comparator<int[]> mo_sComparator(int M){
		return (a,b)->a[0]/M!=b[0]/M?Integer.compare(a[0]/M,b[0]/M):
			Integer.compare(a[1]/M,b[1]/M)*((a[0]/M&1)==0?-1:1);
	}
}
class MathFunction{
	static int[] numberForIntPrime={2,7,61};
	static long[] numberForLongPrime={2,7,61,325,9375,28178,450775,9780504,1795265022};
	static long gcd(long a,long b){
		a=Math.abs(a);
		b=Math.abs(b);
		if(b==0){
			return a;
		}
		long temp;
		while((temp=a%b)!=0){
			a=b;
			b=temp;
		}
		return b;
	}
	static long lcm(long a,long b){
		return a/gcd(a,b)*b;
	}
	static boolean isPrime(long n){
		n=Math.abs(n);
		if(n==2L){
			return true;
		}
		if(n==1L||(n&1L)==0L){
			return false;
		}
		if(n<=4_759_123_141L){
			return isPrimeForInt(n);
		}
		return isPrimeForBigInteger(n);
	}
	static boolean isPrimeForInt(long n){
		long d=n-1;
		while((d&1)==0L){
			d >>= 1;
		}
		for(long a: numberForIntPrime){
			if(a>=n){
				return true;
			}
			long t=d;
			long y=MathFunction.modPow(a,t,n);
			while(t<n-1L&&y!=1&&y!=n-1){
				y=y*y%n;
				t <<= 1;
			}
			if(y!=n-1&&(t&1L)==0){
				return false;
			}
		}
		return true;
	}
	static boolean isPrimeForBigInteger(long n){
		long d=n-1L;
		while((d&1)==0L){
			d >>= 1;
		}
		BigInteger bigN=BigInteger.valueOf(n);
		BigInteger bigNSubOne=bigN.subtract(BigInteger.ONE);
		BigInteger bigD=BigInteger.valueOf(d);
		for(long a: numberForLongPrime){
			if(a>=n){
				return true;
			}
			BigInteger t=bigD;
			BigInteger y=BigInteger.valueOf(a).modPow(t,bigN);
			while(t.compareTo(bigNSubOne)<0&&!y.equals(BigInteger.ONE)&&!y.equals(bigNSubOne)){
				y=y.multiply(y).mod(bigN);
				t=t.shiftLeft(1);
			}
			if(!y.equals(bigNSubOne)&&(t.intValue()&1)==0){
				return false;
			}
		}
		return true;
	}
	static int[] primes(int num){
		if(num<2){
			return new int[0];
		}
		BitSet numbers=new BitSet(num+1);
		numbers.set(2,num+1);
		int limit=(int)Math.sqrt(num);
		int bit=0;
		while(
			rangeCheckClose(
				bit=numbers.nextSetBit(bit+1),
				2,
				limit)){
			for(int j=bit*bit;j<=num;j+=bit){
				numbers.clear(j);
			}
		}
		int[] answer=new int[numbers.cardinality()];
		bit=0;
		for(int i=0;i<answer.length;++i)
			bit=(answer[i]=numbers.nextSetBit(bit+1));
		return answer;
	}
	static long pow(long a,long b){
		long ans=1;
		while(b>0){
			if((b&1)==1){
				ans *= a;
			}
			a *= a;
			b >>= 1;
		}
		return ans;
	}
	static long modPow(long a,long b,long mod){
		long ans=1;
		a %= mod;
		while(b>0){
			if((b&1)==1){
				ans *= a;
			}
			ans %= mod;
			a *= a;
			a %= mod;
			b >>= 1;
		}
		return ans;
	}
	static long fact(int N){
		long ans=1;
		for(int i=2;i<=N;++i){
			ans *= i;
		}
		return ans;
	}
	static long modFact(int N,long mod){
		long ans=1;
		for(int i=2;i<=N;++i){
			ans *= i;
			ans %= mod;
		}
		return ans;
	}
	static long combi(long n,long r){
		if(r<0||n<r){
			return 0;
		}
		long ans=1;
		r=Math.min(n-r,r);
		for(int i=0;i<r;++i){
			ans *= n-i;
			ans /= i+1;
		}
		return ans;
	}
	static long modCombi(long n,long r,long mod){
		if(r<0||n<r){
			return 0;
		}
		long ans=1;
		r=Math.min(n-r,r);
		for(int i=0;i<r;++i){
			ans *= (n-i)%mod;
			ans %= mod;
			ans *= modPow(i+1,mod-2,mod);
			ans %= mod;
		}
		return ans;
	}
	static int isCrossed(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
		long s1=(long)(x1-x2)*(y3-y1)-(long)(y1-y2)*(x3-x1);
		long t1=(long)(x1-x2)*(y4-y1)-(long)(y1-y2)*(x4-x1);
		long s2=(long)(x3-x4)*(y1-y3)-(long)(y3-y4)*(x1-x3);
		long t2=(long)(x3-x4)*(y2-y3)-(long)(y3-y4)*(x2-x3);
		long temp1=s1*t1;
		long temp2=s2*t2;
		if(temp1>0||temp2>0){
			return -1;
		}
		if(temp1==0&&temp2==0){
			return 0;
		}
		return 1;
	}
	static int isCrossed(Point p1,Point p2,Point p3,Point p4){
		return isCrossed(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y,p4.x,p4.y);
	}
	static boolean isConvex(Point... points){
		int n=points.length;
		if(n<3){
			return false;
		}
		if(n==3){
			return true;
		}
		boolean conv=true;
		for(int i=0;i<n;++i){
			int result=isCrossed(points[i],points[(i+2)%n],points[(i+1)%n],points[(i+1+n/2)%n]);
			conv &= result>=0;
		}
		return conv;
	}
	static long remainder(long num,long mod){
		num %= mod;
		if(num<0){
			num += mod;
		}
		return num;
	}
	static int digit(long num){
		if(num<10L){
			return 1;
		}
		if(num<100L){
			return 2;
		}
		if(num<1000L){
			return 3;
		}
		if(num<10000L){
			return 4;
		}
		if(num<100000L){
			return 5;
		}
		if(num<1000000L){
			return 6;
		}
		if(num<10000000L){
			return 7;
		}
		if(num<100000000L){
			return 8;
		}
		if(num<1000000000L){
			return 9;
		}
		if(num<10000000000L){
			return 10;
		}
		if(num<100000000000L){
			return 11;
		}
		if(num<1000000000000L){
			return 12;
		}
		if(num<10000000000000L){
			return 13;
		}
		if(num<100000000000000L){
			return 14;
		}
		if(num<1000000000000000L){
			return 15;
		}
		if(num<10000000000000000L){
			return 16;
		}
		if(num<100000000000000000L){
			return 17;
		}
		if(num<1000000000000000000L){
			return 18;
		}
		return 19;
	}
	static int max(int... nums){
		int ans=Integer.MIN_VALUE;
		for(int num: nums){
			ans=Math.max(ans,num);
		}
		return ans;
	}
	static long max(long... nums){
		long ans=Long.MIN_VALUE;
		for(long num: nums){
			ans=Math.max(ans,num);
		}
		return ans;
	}
	static double max(double... nums){
		double ans=-Double.MIN_VALUE;
		for(double num: nums){
			ans=Math.max(ans,num);
		}
		return ans;
	}
	static <E extends Comparable<E>> E max(E[] nums){
		E ans=nums[0];
		for(E value: nums){
			if(ans.compareTo(value)<0){
				ans=value;
			}
		}
		return ans;
	}
	static int min(int... nums){
		int ans=Integer.MAX_VALUE;
		for(int num: nums){
			ans=Math.min(ans,num);
		}
		return ans;
	}
	static long min(long... nums){
		long ans=Long.MAX_VALUE;
		for(long num: nums){
			ans=Math.min(ans,num);
		}
		return ans;
	}
	static double min(double... nums){
		double ans=Double.MAX_VALUE;
		for(double num: nums){
			ans=Math.min(ans,num);
		}
		return ans;
	}
	static <E extends Comparable<E>> E min(E[] nums){
		E ans=nums[0];
		for(E value: nums){
			if(ans.compareTo(value)>0){
				ans=value;
			}
		}
		return ans;
	}
	static long sum(int... nums){
		long ans=0;
		for(int num: nums){
			ans += num;
		}
		return ans;
	}
	static long sum(long... nums){
		long ans=0;
		for(long num: nums){
			ans += num;
		}
		return ans;
	}
	static long modSum(long mod,int... nums){
		long ans=0;
		for(int num: nums){
			ans += num;
			ans %= mod;
		}
		if(ans<0){
			ans += mod;
		}
		return ans;
	}
	static long modSum(long mod,long... nums){
		long ans=0;
		for(long num: nums){
			ans += num;
			ans %= mod;
		}
		if(ans<0){
			ans += mod;
		}
		return ans;
	}
	static long sum(int[] nums,int from,int to){
		long ans=0;
		for(int i=from;i<to;++i){
			ans += nums[i];
		}
		return ans;
	}
	static long sum(long[] nums,int from,int to){
		long ans=0;
		for(int i=from;i<to;++i){
			ans += nums[i];
		}
		return ans;
	}
	static long modSum(int[] nums,int from,int to,long mod){
		long ans=0;
		for(int i=from;i<to;++i){
			ans += nums[i];
			ans %= mod;
		}
		if(ans<0){
			ans += mod;
		}
		return ans;
	}
	static long modSum(long[] nums,int from,int to,long mod){
		long ans=0;
		for(int i=from;i<to;++i){
			ans += nums[i];
			ans %= mod;
		}
		if(ans<0){
			ans += mod;
		}
		return ans;
	}
	static boolean rangeCheck(int num,int l,int r){
		return l<=num&&num<r;
	}
	static boolean rangeCheck(long num,long l,long r){
		return l<=num&&num<r;
	}
	static boolean rangeCheck(double num,double l,double r){
		return l<=num&&num<r;
	}
	static <E extends Comparable<E>> boolean rangeCheck(E num,E l,E r){
		return 0<=num.compareTo(l)&&num.compareTo(r)<0;
	}
	static boolean rangeCheckOpen(int num,int l,int r){
		return l<num&&num<r;
	}
	static boolean rangeCheckOpen(long num,long l,long r){
		return l<num&&num<r;
	}
	static boolean rangeCheckOpen(double num,double l,double r){
		return l<num&&num<r;
	}
	static <E extends Comparable<E>> boolean rangeCheckOpen(E num,E l,E r){
		return 0<num.compareTo(l)&&num.compareTo(r)<0;
	}
	static boolean rangeCheckClose(int num,int l,int r){
		return l<=num&&num<=r;
	}
	static boolean rangeCheckClose(long num,long l,long r){
		return l<=num&&num<=r;
	}
	static boolean rangeCheckClose(double num,double l,double r){
		return l<=num&&num<=r;
	}
	static <E extends Comparable<E>> boolean rangeCheckClose(E num,E l,E r){
		return 0<=num.compareTo(l)&&num.compareTo(r)<=0;
	}
	static boolean rangeCheckSubClose(int num,int l,int r){
		return l<num&&num<=r;
	}
	static boolean rangeCheckSubClose(long num,long l,long r){
		return l<num&&num<=r;
	}
	static boolean rangeCheckSubClose(double num,double l,double r){
		return l<num&&num<=r;
	}
	static <E extends Comparable<E>> boolean rangeCheckSubClose(E num,E l,E r){
		return 0<num.compareTo(l)&&num.compareTo(r)<=0;
	}
	static int mex(int... nums){
		BitSet set=new BitSet(nums.length);
		for(int num: nums)
			if(num<nums.length)
				set.set(num);
		return set.nextClearBit(0);
	}
}
class Searcher{
	static int CYCLE_COUNT=Double.MAX_EXPONENT+53;
	static int downSearch(int[] array,int value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int downSearch(long[] array,long value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int downSearch(double[] array,double value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int downSearch(char[] array,int value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch(E[] array,E value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c].compareTo(value)>0){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int downSearch(List<E> list,E value){
		int a=0, b=list.size()-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(list.get(c).compareTo(value)>0){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int downSearch(int a,int b,int value,IntUnaryOperator func){
		int ans=a-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsInt(c)>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static long downSearch(long a,long b,long value,LongUnaryOperator func){
		long ans=a-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsLong(c)>value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static double search(double a,double b,double value,DoubleUnaryOperator func){
		double ans=a-Math.abs(a), c;
		for(int $=0;$<CYCLE_COUNT;++$){
			c=(a+b)/2;
			if(func.applyAsDouble(c)>value){
				b=c;
			}
			else{
				a=(ans=c);
			}
		}
		return ans;
	}
	static boolean contains(int[] array,int value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(long[] array,long value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(double[] array,double value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(char[] array,char value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static <E extends Comparable<E>> boolean contains(E[] array,E value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			int result=array[c].compareTo(value);
			if(result>0){
				b=c-1;
			}
			else if(result<0){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static <E extends Comparable<E>> boolean contains(List<E> list,E value){
		int a=0, b=list.size()-1, c;
		while(a-b<1){
			c=(a+b)/2;
			int result=list.get(c).compareTo(value);
			if(result>0){
				b=c-1;
			}
			else if(result<0){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(int a,int b,int value,IntUnaryOperator func){
		int c;
		while(a-b<1){
			c=(a+b)/2;
			int num=func.applyAsInt(c);
			if(num>value){
				b=c-1;
			}
			else if(num<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(long a,long b,long value,LongUnaryOperator func){
		long c;
		while(a-b<1){
			c=(a+b)/2;
			long num=func.applyAsLong(c);
			if(num>value){
				b=c-1;
			}
			else if(num<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static boolean contains(double a,double b,double value,DoubleUnaryOperator func){
		double c;
		for(int $=0;$<CYCLE_COUNT;++$){
			c=(a+b)/2;
			double num=func.applyAsDouble(c);
			if(num>value){
				b=c-1;
			}
			else if(num<value){
				a=c+1;
			}
			else{
				return true;
			}
		}
		return false;
	}
	static int search(int[] array,int value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static int search(long[] array,long value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static int search(double[] array,double value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static int search(char[] array,char value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=c-1;
			}
			else if(array[c]<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static <E extends Comparable<E>> int search(E[] array,E value){
		int a=0, b=array.length-1, c;
		while(a-b<1){
			c=(a+b)/2;
			int result=array[c].compareTo(value);
			if(result>0){
				b=c-1;
			}
			else if(result<0){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static <E extends Comparable<E>> int search(List<E> list,E value){
		int a=0, b=list.size()-1, c;
		while(a-b<1){
			c=(a+b)/2;
			int result=list.get(c).compareTo(value);
			if(result>0){
				b=c-1;
			}
			else if(result<0){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return -1;
	}
	static int search(int a,int b,int value,IntUnaryOperator func){
		int c;
		while(a-b<1){
			c=(a+b)/2;
			int num=func.applyAsInt(c);
			if(num>value){
				b=c-1;
			}
			else if(num<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return a-1;
	}
	static long search(long a,long b,long value,LongUnaryOperator func){
		long c;
		while(a-b<1){
			c=(a+b)/2;
			long num=func.applyAsLong(c);
			if(num>value){
				b=c-1;
			}
			else if(num<value){
				a=c+1;
			}
			else{
				return c;
			}
		}
		return a-1;
	}
	static int upSearch(int[] array,int value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int upSearch(long[] array,long value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int upSearch(double[] array,double value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int upSearch(char[] array,char value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch(E[] array,E value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c].compareTo(value)>=0){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int upSearch(List<E> list,E value){
		int a=0, b=list.size()-1, ans=list.size(), c;
		while(a-b<1){
			c=(a+b)/2;
			if(list.get(c).compareTo(value)>=0){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int upSearch(int a,int b,int value,IntUnaryOperator func){
		int ans=b+1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsInt(c)>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static long upSearch(long a,long b,long value,LongUnaryOperator func){
		long ans=b+1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsLong(c)>=value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int underSearch(int[] array,int value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int underSearch(long[] array,long value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int underSearch(double[] array,double value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int underSearch(char[] array,char value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch(E[] array,E value){
		int a=0, b=array.length-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c].compareTo(value)>=0){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int underSearch(List<E> list,E value){
		int a=0, b=list.size()-1, ans=-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(list.get(c).compareTo(value)>=0){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int underSearch(int a,int b,int value,IntUnaryOperator func){
		int ans=a-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsInt(c)>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static long underSearch(long a,long b,long value,LongUnaryOperator func){
		long ans=a-1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsLong(c)>=value){
				b=c-1;
			}
			else{
				a=(ans=c)+1;
			}
		}
		return ans;
	}
	static int overSearch(int[] array,int value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int overSearch(long[] array,long value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int overSearch(double[] array,double value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int overSearch(char[] array,char value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c]>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch(E[] array,E value){
		int a=0, b=array.length-1, ans=array.length, c;
		while(a-b<1){
			c=(a+b)/2;
			if(array[c].compareTo(value)>0){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static <E extends Comparable<E>> int overSearch(List<E> list,E value){
		int a=0, b=list.size()-1, ans=list.size(), c;
		while(a-b<1){
			c=(a+b)/2;
			if(list.get(c).compareTo(value)>0){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int overSearch(int a,int b,int value,IntUnaryOperator func){
		int ans=b+1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsInt(c)>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static long overSearch(long a,long b,long value,LongUnaryOperator func){
		long ans=b+1, c;
		while(a-b<1){
			c=(a+b)/2;
			if(func.applyAsLong(c)>value){
				b=(ans=c)-1;
			}
			else{
				a=c+1;
			}
		}
		return ans;
	}
	static int linearSearch(int[] array,int value){
		for(int i=0;i<array.length;++i){
			if(array[i]==value){
				return i;
			}
		}
		return -1;
	}
	static int linearSearch(long[] array,long value){
		for(int i=0;i<array.length;++i){
			if(array[i]==value){
				return i;
			}
		}
		return -1;
	}
	static int linearSearch(double[] array,double value){
		for(int i=0;i<array.length;++i){
			if(array[i]==value){
				return i;
			}
		}
		return -1;
	}
	static int linearSearch(char[] array,char value){
		for(int i=0;i<array.length;++i){
			if(array[i]==value){
				return i;
			}
		}
		return -1;
	}
	static <E extends Comparable<E>> int linearSearch(E[] array,E value){
		for(int i=0;i<array.length;++i){
			if(array[i].compareTo(value)==0){
				return i;
			}
		}
		return -1;
	}
	static <E extends Comparable<E>> int linearSearch(List<E> list,E value){
		for(int i=0;i<list.size();++i){
			if(list.get(i).compareTo(value)==0){
				return i;
			}
		}
		return -1;
	}
}
class Matrix{
	long[][] matrix;
	Matrix(int H,int W,long def){
		matrix=new long[H][W];
		if(def!=0){
			for(long[] mat: matrix){
				Arrays.fill(mat,def);
			}
		}
	}
	Matrix(int H,int W){
		this(H,W,0);
	}
	Matrix(Dimension d,long def){
		this(d.height,d.width,def);
	}
	Matrix(long[][] mat){
		matrix=new long[mat.length][];
		for(int i=0;i<mat.length;++i){
			matrix[i]=Arrays.copyOf(mat[i],mat[i].length);
		}
	}
	long get(int i,int j){
		return matrix[i][j];
	}
	long set(int i,int j,long value){
		return matrix[i][j]=value;
	}
	Matrix copy(){
		return new Matrix(matrix);
	}
	Dimension size(){
		return new Dimension(matrix[0].length,matrix.length);
	}
	Matrix add(Matrix m){
		if(!size().equals(m.size())){
			throw new IllegalArgumentException("matrix size is not same");
		}
		Matrix ans=new Matrix(size(),0);
		for(int i=0;i<matrix.length;++i){
			for(int j=0;j<matrix[i].length;++j){
				ans.set(i,j,matrix[i][j]+m.get(i,j));
			}
		}
		return ans;
	}
	Matrix subtract(Matrix m){
		if(!size().equals(m.size())){
			throw new IllegalArgumentException("matrix size is not same");
		}
		Matrix ans=new Matrix(size(),0);
		for(int i=0;i<matrix.length;++i){
			for(int j=0;j<matrix[i].length;++j){
				ans.set(i,j,matrix[i][j]-m.get(i,j));
			}
		}
		return ans;
	}
	Matrix multiply(Matrix m){
		if(size().width!=m.size().height){
			throw new IllegalArgumentException("matrix length is not same");
		}
		Matrix ans=new Matrix(size().height,m.size().width);
		Dimension size=ans.size();
		int len=size().width;
		for(int i=0;i<size.height;++i){
			for(int j=0;j<size.width;++j){
				long sum=0;
				for(int k=0;k<len;++k){
					sum += matrix[i][k]*m.get(k,j);
				}
				ans.set(i,j,sum);
			}
		}
		return ans;
	}
	Matrix modAdd(Matrix m,long mod){
		if(!size().equals(m.size())){
			throw new IllegalArgumentException("matrix size is not same");
		}
		Matrix ans=new Matrix(size(),0);
		for(int i=0;i<matrix.length;++i){
			for(int j=0;j<matrix[i].length;++j){
				ans.set(i,j,MathFunction.remainder(matrix[i][j]+m.get(i,j),mod));
			}
		}
		return ans;
	}
	Matrix modSubtract(Matrix m,long mod){
		if(!size().equals(m.size())){
			throw new IllegalArgumentException("matrix size is not same");
		}
		Matrix ans=new Matrix(size(),0);
		for(int i=0;i<matrix.length;++i){
			for(int j=0;j<matrix[i].length;++j){
				ans.set(i,j,MathFunction.remainder(matrix[i][j]-m.get(i,j),mod));
			}
		}
		return ans;
	}
	Matrix modMultiply(Matrix m,long mod){
		if(size().width!=m.size().height){
			throw new IllegalArgumentException("matrix length is not same");
		}
		Matrix ans=new Matrix(size().height,m.size().width);
		Dimension size=ans.size();
		int len=size().width;
		for(int i=0;i<size.height;++i){
			for(int j=0;j<size.width;++j){
				long sum=0;
				for(int k=0;k<len;++k){
					sum=MathFunction.remainder(sum+matrix[i][k]*m.get(k,j),mod);
				}
				ans.set(i,j,sum);
			}
		}
		return ans;
	}
	static Matrix pow(Matrix original,Matrix pw,long exp){
		Matrix a=original.copy();
		Matrix b=pw.copy();
		while(0<exp){
			if((exp&1)==1){
				a=b.multiply(a);
			}
			b=b.multiply(b);
			exp >>= 1;
		}
		return a;
	}
	static Matrix modPow(Matrix original,Matrix pw,long exp,long mod){
		Matrix a=original.copy();
		Matrix b=pw.copy();
		while(0<exp){
			if((exp&1)==1){
				a=b.modMultiply(a,mod);
			}
			b=b.modMultiply(b,mod);
			exp >>= 1;
		}
		return a;
	}
	long determinant(){
		return determinant(matrix);
	}
	static long determinant(long[][] mat){
		if(mat.length==1){
			return mat[0][0];
		}
		long[][] miniMat=new long[mat.length-1][mat.length-1];
		for(int i=1;i<mat.length;++i){
			System.arraycopy(mat[i],1,miniMat[i-1],0,miniMat.length);
		}
		long ans=mat[0][0]*determinant(miniMat);
		for(int i=1;i<mat.length;++i){
			for(int j=1;j<mat.length;++j){
				miniMat[j-1][i-1]=mat[j][i-1];
			}
			long num=mat[0][i]*determinant(miniMat);
			ans += i%2==0?num:-num;
		}
		return ans;
	}
	@Override public String toString(){
		StringBuilder ans=new StringBuilder();
		ans.append(Arrays.toString(matrix[0]));
		for(int i=1;i<matrix.length;++i){
			ans.append("\n");
			ans.append(Arrays.toString(matrix[i]));
		}
		return ans.toString();
	}
}
class RollingHash implements Comparable<RollingHash>{
	static long BASE=new Random().nextInt(1000)+Character.MAX_VALUE+1,MASK30=(1L<<30)-1,MASK31=(1L<<31)-1,MOD=(1L<<61)-1,MASK61=MOD;
	long[]hash;
	String string;
	RollingHash(String str){string=str;hash=new long[str.length()+1];roll();}
	void roll(){int len=string.length();for(int i=1;i<=len;++i){hash[i]=multiply(hash[i-1],BASE)+string.charAt(i-1)-' '+1;if(MOD<=hash[i])hash[i]-=MOD;}}
	static long multiply(long a,long b){long au=a>>31,ad=a&MASK31,bu=b>>31,bd=b&MASK31,mid=ad*bu+au*bd,midu=mid>>30,midd=mid&MASK30;return mod(au*bu*2+midu+(midd<<31)+ad*bd);}
	static long mod(long x){long xu=x>>61,xd=x&MASK61,ans=xu+xd;if(MOD<=ans)ans-=MOD;return ans;}
	long getHash(int l,int r){return(hash[r]-multiply(hash[l],modBasePow(r-l))+MOD)%MOD;}
	static long modBasePow(long b){long ans=1,a=BASE;while(b>0){if((b&1)==1)ans=multiply(ans,a);a=multiply(a,a);b>>=1;}return ans;}
	boolean equals(RollingHash rh,int l1,int r1,int l2,int r2){return r1-l1!=r2-l2?false:getHash(l1,r1)==rh.getHash(l2,r2);}
	int length(){return string.length();}
	@Override public int hashCode(){return string.hashCode();}
	@Override public String toString(){return string;}
	@Override public boolean equals(Object o){return o instanceof RollingHash rh?equals(rh,0,length(),0,rh.length()):false;}
	@Override public int compareTo(RollingHash rh){return string.compareTo(rh.toString());}
	int compareTo(String str){return string.compareTo(str);}
	char charAt(int i){return string.charAt(i);}
	int compareToIgnoreCase(RollingHash rh){return string.compareToIgnoreCase(rh.toString());}
	int compareToIgnoreCase(String str){return string.compareToIgnoreCase(str);}
	void concat(RollingHash rh){concat(rh.toString());}
	void concat(String str){string=string.concat(str);hash=new long[string.length()+1];roll();}
	boolean contains(RollingHash rh){var hash=rh.getHash(0,rh.length());int len=length()-rh.length();for(int i=0;i<=len;++i)if(hash==getHash(i,rh.length()+i))return true;return false;}
	boolean contains(String str){return indexOf(str)!=-1;}
	int indexOf(int ch){return indexOf(ch,0);}
	int indexOf(int ch,int fromIndex){int len=length();for(int i=fromIndex;i<len;++i)if(string.charAt(i)==ch)return i;return -1;}
	int indexOf(String str){return indexOf(str,0);}
	int indexOf(String str,int fromIndex){long hash=0;for(char c: str.toCharArray()){hash=multiply(hash,BASE)+c-' '+1;if(MOD<=hash)hash-=MOD;}int len=length()-str.length();for(int i=fromIndex;i<=len;++i)if(hash==getHash(i,str.length()+i))return i;return -1;}
	boolean isEmpty(){return length()==0;}
	int lastIndexOf(int ch,int fromIndex){for(int i=fromIndex;i>=0;--i)if(string.charAt(i)==ch)return i;return -1;}
	int lastIndexOf(int ch){return lastIndexOf(ch,length()-1);}
	static RollingHash valueOf(boolean b){return new RollingHash(b?"true":"false");}
	static RollingHash valueOf(char c){return new RollingHash(""+c);}
	static RollingHash valueOf(char[] c){return new RollingHash(String.valueOf(c,0,c.length));}
	static RollingHash valueOf(char[] c,int offset,int count){return new RollingHash(String.valueOf(c,offset,count));}
	static RollingHash valueOf(double d){return new RollingHash(String.valueOf(d));}
	static RollingHash valueOf(float f){return new RollingHash(String.valueOf(f));}
	static RollingHash valueOf(int i){return new RollingHash(String.valueOf(i));}
	static RollingHash valueOf(long l){return new RollingHash(String.valueOf(l));}
	static RollingHash valueOf(Object obj){return new RollingHash(String.valueOf(obj));}
}
@SuppressWarnings("unchecked")abstract class SegmentTree<E>{
	int N,size;
	E def;
	Object[]node;
	SegmentTree(int n,E def,boolean is1indexed){int num=2;while(num<n<<1)num<<=1;N=num;size=(num>>1)-(is1indexed?1:0);node=new Object[N];this.def=def;Arrays.fill(node,this.def);}
	SegmentTree(E[]arr,E def,boolean is1indexed){int num=2;while(num<arr.length<<1)num<<=1;N=num;size=num>>1-(is1indexed?1:0);node=new Object[N];this.def=def;System.arraycopy(arr,0,node,N>>1,arr.length);for(int i=arr.length+(N>>1);i<N;i++)node[i]=def;updateAll();}
	SegmentTree(int n,E def){this(n,def,false);}
	void updateAll(){for(int i=(N>>1)-1;i>0;i--)node[i]=function((E)node[i<<1],(E)node[(i<<1)+1]);}
	void update(int n,E value){n+=size;node[n]=value;n>>=1;while(n>0){node[n]=function((E)node[n<<1],(E)node[(n<<1)+1]);n>>=1;}}
	E get(int a){return(E)node[a+size];}
	E answer(){return(E)node[1];}
	E query(int l,int r){l+=size;r+=size;E answer=def;while(l>0&&r>0&&l<=r){if(l%2==1)answer=function((E)node[l++],answer);l>>=1;if(r%2==0)answer=function(answer,(E)node[r--]);r>>=1;}return answer;}
	abstract E function(E a,E b);
}
@SuppressWarnings("unchecked")abstract class LazySegmentTree<S,F>{
	int size,log;
	S defaultS;
	F defaultF;
	S[]node;
	F[]lazy;
	LazySegmentTree(int N,S defaultS,F defaultF){this(N,defaultS,defaultF,false);}
	LazySegmentTree(int N,S defaultS,F defaultF,boolean is1indexed){this.log=32-Integer.numberOfLeadingZeros(N-1);this.size=(1<<log)-(is1indexed?1:0);this.defaultS=defaultS;this.defaultF=defaultF;this.node=(S[])new Object[1<<log+1];this.lazy=(F[])new Object[1<<log+1];clear();}
	LazySegmentTree(S[]defaultValues,S defaultS,F defaultF,boolean is1indexed){this(defaultValues.length,defaultS,defaultF,is1indexed);updateAll(defaultValues);}
	void clear(){Arrays.fill(this.node,this.defaultS);Arrays.fill(this.lazy,this.defaultF);}
	void updateAll(S[]defaultValues){System.arraycopy(defaultValues,0,node,1<<log,defaultValues.length);for(int i=(1<<log)-1;i>0;i--)node[i]=function(node[i<<1],node[i<<1|1]);}
	void spread(int index){if(lazy[index]!=defaultF){int l=index<<1,r=index<<1|1;node[l]=mapping(node[l],lazy[index]);node[r]=mapping(node[r],lazy[index]);lazy[l]=composition(lazy[l],lazy[index]);lazy[r]=composition(lazy[r],lazy[index]);lazy[index]=defaultF;}}
	void spreadLine(int from){for(int i=log;i>0;i--)spread(from>>i);}
	void spreadRange(int l,int r){for(int i=log;i>0;i--){if((l>>i<<i)!=l)spread(l>>i);if((r>>i<<i)!=r)spread(r>>i);}}
	void update(int index){while((index>>=1)>0)node[index]=function(node[index<<1],node[index<<1|1]);}
	void update(int l,int r){for(int i=1;i<=log;i++){int subL=l>>i,subR=r>>i;if((subL<<i)!=l)node[subL]=function(node[subL<<1],node[subL<<1|1]);if((subR<<i)!=r)node[subR]=function(node[subR<<1],node[subR<<1|1]);}}
	void update(int index,S x){index+=size;spreadLine(index);node[index]=x;update(index);}
	S get(int index){index+=size;spreadLine(index);return node[index];}
	S query(int l,int r){l+=size;r+=size;spreadRange(l,r);S sumL=defaultS,sumR=defaultS;while(l<r){if((l&1)==1)sumL=function(sumL,node[l++]);if((r&1)==1)sumR=function(node[--r],sumR);l>>=1;r>>=1;}return function(sumL,sumR);}
	S answer(){return node[1];}
	void apply(int index,F f){index+=size;spreadLine(index);node[index]=mapping(node[index],f);update(index);}
	void apply(int l,int r,F f){l+=size;r+=size;spreadRange(l,r);int subL=l,subR=r;while(subL<subR){if((subL&1)==1){node[subL]=mapping(node[subL],f);lazy[subL]=composition(lazy[subL++],f);}if((subR&1)==1){node[--subR]=mapping(node[subR],f);lazy[subR]=composition(lazy[subR],f);}subL>>=1;subR>>=1;}update(l,r);}
	abstract S function(S s1,S s2);
	abstract F composition(F f1,F f2);
	abstract S mapping(S s,F f);
}
class UnionFind{
	int[]par,rank,size,path;
	int count;
	UnionFind(int N){count=N;par=new int[N];rank=new int[N];size=new int[N];path=new int[N];Arrays.fill(par,-1);Arrays.fill(size,1);}
	int root(int ind){return par[ind]==-1?ind:(par[ind]=root(par[ind]));}
	boolean isSame(int x,int y){return root(x)==root(y);}
	boolean unite(int x,int y){int rx=root(x);int ry=root(y);++path[rx];if(rx==ry)return false;if(rank[rx]<rank[ry]){int temp=rx;rx=ry;ry=temp;}par[ry]=rx;if(rank[rx]==rank[ry])++rank[rx];path[rx]+=path[ry];size[rx]+=size[ry];--count;return true;}
	int groupCount(){return count;}
	int pathCount(int x){return path[root(x)];}
	int size(int x){return size[root(x)];}
}
class SimpleScanner{
	int BUFF_SIZE=1<<17,point,length;
	InputStream is;
	byte[]buff;
	SimpleScanner(InputStream is){this.is=is;buff=new byte[BUFF_SIZE];point=length=0;}
	void reload(){do{try{length=is.read(buff,point=0,BUFF_SIZE);}catch(IOException e){e.printStackTrace();System.exit(1);}}while(length==-1);}
	byte read(){if(point==length)reload();return buff[point++];}
	byte nextByte(){var c=read();while(c<=' ')c=read();return c;}
	int nextInt(){int ans=0;var c=nextByte();var negate=c=='-';if(!MathFunction.rangeCheckClose(c,'0','9'))c=read();while(MathFunction.rangeCheckClose(c,'0','9')){ans=ans*10+c-'0';c=read();}return negate?-ans:ans;}
	long nextLong(){long ans=0;var c=nextByte();var negate=c=='-';if(!MathFunction.rangeCheckClose(c,'0','9'))c=read();while(MathFunction.rangeCheckClose(c,'0','9')){ans=ans*10L+c-'0';c=read();}return negate?-ans:ans;}
	char nextChar(){return(char)nextByte();}
	String next(){var ans=new StringBuilder();var c=nextByte();while(c>' '){ans.append((char)c);c=read();}return ans.toString();}
	BigInteger nextBigInteger(){return new BigInteger(next());}
	byte[]nextByte(int n){var ans=new byte[n];for(int i=0;i<n;++i)ans[i]=nextByte();return ans;}
	int[]nextInt(int n){var ans=new int[n];for(int i=0;i<n;++i)ans[i]=nextInt();return ans;}
	long[]nextLong(int n){var ans=new long[n];for(int i=0;i<n;++i)ans[i]=nextLong();return ans;}
	String[]next(int n){var ans=new String[n];for(int i=0;i<n;++i)ans[i]=next();return ans;}
	byte[][]nextByte(int n,int m){var ans=new byte[n][];for(int i=0;i<n;++i)ans[i]=nextByte(m);return ans;}
	int[][]nextInt(int n,int m){var ans=new int[n][];for(int i=0;i<n;++i)ans[i]=nextInt(m);return ans;}
	long[][]nextLong(int n,int m){var ans=new long[n][];for(int i=0;i<n;++i)ans[i]=nextLong(m);return ans;}
	String[][]next(int n,int m){var ans=new String[n][];for(int i=0;i<n;++i)ans[i]=next(m);return ans;}
	char[]nextCharArray(){return next().toCharArray();}
	char[][]nextCharArray(int n){var ans=new char[n][];for(int i=0;i<n;++i)ans[i]=nextCharArray();return ans;}
	int[][]nextGraph(int N,int M){if(M==0)return new int[N+1][0];var ans=new int[N+1][];var count=new int[N+1];var path=nextInt(M,2);for(var temp:path){++count[temp[0]];++count[temp[1]];}for(int i=1;i<=N;++i)ans[i]=new int[count[i]];for(var temp:path){ans[temp[0]][--count[temp[0]]]=temp[1];ans[temp[1]][--count[temp[1]]]=temp[0];}ans[0]=new int[0];return ans;}
	Point nextPoint(){return new Point(nextInt(),nextInt());}
	Point[]nextPoint(int n){var ans=new Point[n];for(int i=0;i<n;++i)ans[i]=nextPoint();return ans;}
	void close(){try{is.close();}catch(IOException e){e.printStackTrace();System.exit(1);}}
}
class SimpleWriter implements Closeable,Flushable,AutoCloseable{
	boolean autoFlush;
	SimpleOutputStream out;
	static char[]charsOfReturn;
	static byte[]integerBuffer,MIN_VALUE_ARRAY;
	static byte ZERO;
	static{charsOfReturn=System.lineSeparator().toCharArray();integerBuffer=new byte[20];integerBuffer[0]='-';ZERO='0';MIN_VALUE_ARRAY=new byte[]{'-','9','2','2','3','3','7','2','0','3','6','8','5','4','7','7','5','8','0','8'};}
	SimpleWriter(OutputStream out){this(out,false);}
	SimpleWriter(OutputStream out,boolean autoFlush){this.out=new SimpleOutputStream(out,1<<17);this.autoFlush=autoFlush;}
	public void flush(){try{out.flush();}catch(Exception x){x.printStackTrace();System.exit(1);}}
	public void close(){try{if(out==null)return;out.close();out=null;}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void write(int c){try{out.write(c);}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void write(char[]buf,int off,int len){try{out.write(buf,off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void write(byte[]buf,int off,int len){try{out.write(buf,off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void write(char[]buf){write(buf,0,buf.length);}
	void write(byte[]buf){write(buf,0,buf.length);}
	void write(String s,int off,int len){try{out.write(s.toCharArray(),off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void write(String s){write(s.toCharArray(),0,s.length());}
	void newLine(){try{out.write(charsOfReturn,0,charsOfReturn.length);if(autoFlush)out.flush();}catch(Exception x){x.printStackTrace();System.exit(1);}}
	void print(boolean b){write(b?"true":"false");}
	void print(char c){write(c);}
	void print(long l){if(l==Long.MIN_VALUE)write(MIN_VALUE_ARRAY);else{long num=Math.abs(l);int len=MathFunction.digit(num);for(int i=len;i>0;i--){integerBuffer[i]=(byte)(num%10+ZERO);num/=10;}if(l<0)write(integerBuffer,0,len+1);else write(integerBuffer,1,len);}}
	void print(float f){write(String.valueOf(f).toCharArray());}
	void print(double d){write(String.valueOf(d).toCharArray());}
	void print(char[]s){write(s);}
	void print(Object obj){write(obj.toString().toCharArray());}
	void println(){newLine();}
	void println(boolean x){print(x);println();}
	void println(char x){print(x);println();}
	void println(int x){print(x);println();}
	void println(long x){print(x);println();}
	void println(float x){print(x);println();}
	void println(double x){print(x);println();}
	void println(char[]x){print(x);println();}
	void println(String x){print(x);println();}
	void println(Object x){print(x);println();}
	SimpleWriter printf(String format,Object...args){print(String.format(format,args));return this;}
	SimpleWriter append(CharSequence csq){write(String.valueOf(csq).toCharArray());return this;}
	SimpleWriter append(CharSequence csq,int start,int end){if(csq==null)csq="null";return append(csq.subSequence(start,end));}
	SimpleWriter append(char c){write(c);return this;}
	void print(int[]array){print(array,' ');}
	void print(int[]array,String str){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
	void print(int[]array,char c){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
	void print(int[][]array){print(array,' ');}
	void print(int[][]arrays,String str){if(arrays.length==0)return;print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
	void print(int[][]arrays,char c){if(arrays.length==0)return;print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
	void println(int[]array){print(array,' ');println();}
	void println(int[]array,String str){print(array,str);println();}
	void println(int[]array,char c){print(array,c);println();}
	void println(int[][]array){print(array,' ');println();}
	void println(int[][]arrays,String str){print(arrays,str);println();}
	void println(int[][]arrays,char c){print(arrays,c);println();}
	void print(long[]array){print(array,' ');}
	void print(long[]array,String str){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
	void print(long[]array,char c){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
	void print(long[][]array){print(array,' ');}
	void print(long[][]arrays,String str){if(arrays.length==0)return;print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
	void print(long[][]arrays,char c){if(arrays.length==0)return;print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
	void println(long[]array){println(array,' ');}
	void println(long[]array,String str){print(array,str);println();}
	void println(long[]array,char c){print(array,c);println();}
	void println(long[][]array){println(array,' ');}
	void println(long[][]arrays,String str){print(arrays,str);println();}
	void println(long[][]arrays,char c){print(arrays,c);println();}
	void print(double[]array){print(array,' ');}
	void print(double[]array,String str){print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
	void print(double[]array,char c){print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
	void print(double[][]array){print(array,' ');}
	void print(double[][]arrays,String str){print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
	void print(double[][]arrays,char c){print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
	void println(double[]array){println(array,' ');}
	void println(double[]array,String str){print(array,str);println();}
	void println(double[]array,char c){print(array,c);println();}
	void println(double[][]array){println(array,' ');}
	void println(double[][]arrays,String str){print(arrays,str);println();}
	void println(double[][]arrays,char c){print(arrays,c);println();}
	void println(char[]cs,String str){print(cs[0]);for(int i=1;i<cs.length;++i){print(str);print(cs[i]);}println();}
	void println(char[]cs,char c){print(cs[0]);for(int i=1;i<cs.length;++i){print(c);print(cs[i]);}println();}
	void println(char[][]cs){for(char[]c:cs)println(c);}
	void println(char[][]cs,String str){for(char[]c:cs)println(c,str);}
	void println(char[][]cs,char c){for(char[]cc:cs)println(cc,c);}
	<E>void print(E[]array){print(array,' ');}
	<E>void print(E[]array,String str){print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
	<E>void print(E[]array,char c){print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
	<E>void print(E[][]arrays){print(arrays,' ');}
	<E>void print(E[][]arrays,String str){print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
	<E>void print(E[][]arrays,char c){print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
	<E>void println(E[]array){println(array,' ');}
	<E>void println(E[]array,String str){print(array,str);println();}
	<E>void println(E[]array,char c){print(array,c);println();}
	<E>void println(E[][]arrays){println(arrays,' ');}
	<E>void println(E[][]arrays,String str){print(arrays,str);println();}
	<E>void println(E[][]arrays,char c){print(arrays,c);println();}
	<E>void println(List<E>list){println(list,' ');}
	<E>void println(List<E>list,String str){if(list.size()>0){print(list.get(0));for(int i=1;i<list.size();++i){print(str);print(list.get(i));}}println();}
	<E>void println(List<E>list,char c){if(list.size()>0){print(list.get(0));for(int i=1;i<list.size();++i){print(c);print(list.get(i));}}println();}
	class SimpleOutputStream{
		byte[] buf;
		int count;
		OutputStream out;
		SimpleOutputStream(OutputStream out,int size){this.out=out;if(size<=0)throw new IllegalArgumentException("Buffer size <= 0");buf=new byte[size];}
		void flushBuffer()throws IOException{if(count>0){out.write(buf,0,count);count=0;}}
		void write(int b)throws IOException{if(count>=buf.length)flushBuffer();buf[count++]=(byte)b;}
		void write(char[]ch,int off,int len)throws IOException{if(len>=buf.length){flushBuffer();out.write(parseByteArray(ch,off,len),0,len);return;}if(len>buf.length-count)flushBuffer();for(int i=0;i<len;i++)buf[count+i]=(byte)ch[i+off];count+=len;}
		byte[]parseByteArray(char[]ch,int off,int len){var ans=new byte[len];for(int i=0;i<len;i++)ans[i]=(byte)ch[i+off];return ans;}
		void write(byte[]b,int off,int len)throws IOException{if(len>=buf.length){flushBuffer();out.write(b,off,len);return;}if(len>buf.length-count)flushBuffer();System.arraycopy(b,off,buf,count,len);count+=len;}
		void flush() throws IOException{flushBuffer();out.flush();}
		void close() throws IOException{flush();out.close();out=null;}
	}
}