結果
| 問題 | No.2825 Sum of Scores of Sets of Specified Sections |
| ユーザー |
 viral8
|
| 提出日時 | 2024-04-24 22:31:14 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 62,650 bytes |
| コンパイル時間 | 7,575 ms |
| コンパイル使用メモリ | 110,408 KB |
| 実行使用メモリ | 73,252 KB |
| 最終ジャッジ日時 | 2024-07-26 20:01:23 |
| 合計ジャッジ時間 | 9,957 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 137 ms
55,168 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
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;}
}
}