GitHub Viewer
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
/**
* Author : joney_000[developer.jaswant@gmail.com]
* Algorithm : Extended Euclid Algo: find 3 things X, Y, GCD(A, B) Such that X * A + Y * B = GCD(A, B)
* Time : O(MAX(A, B)) Space : O(MAX(A, B))
* Platform : Codeforces
* Ref : https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/
*/
class Solution{
private InputStream inputStream ;
private OutputStream outputStream ;
private FastReader in ;
private PrintWriter out ;
private final int BUFFER = 100005;
private final long mod = 1000000000+7;
private final int INF = Integer.MAX_VALUE;
private final long INF_L = Long.MAX_VALUE / 10;
public Solution(){}
public Solution(boolean stdIO)throws FileNotFoundException{
// stdIO = false;
if(stdIO){
inputStream = System.in;
outputStream = System.out;
}else{
inputStream = new FileInputStream("input.txt");
outputStream = new FileOutputStream("output.txt");
}
in = new FastReader(inputStream);
out = new PrintWriter(outputStream);
}
final int MAXN = (int)1e3 + 1;
int [][]matrix = new int[MAXN][MAXN];
void run()throws Exception{
int tests = i();
for(int testCase = 1; testCase = mod)ans %= mod;
if(b % 2 == 1)ans = mulMod(a, ans, mod);
if(ans >= mod)ans %= mod;
return ans;
}
// 20*20 nCr Pascal Table
long[][] ncrTable(){
long ncr[][] = new long[21][21];
for(int i = 0; i '9'){
throw new InputMismatchException ();
}
res *= 10;
res += c - '0';
c = read ();
}
if (c == '.'){
c = read ();
double m = 1;
while (!isSpaceChar (c)){
if (c == 'e' || c == 'E'){
return res * Math.pow (10, nextInt ());
}
if (c < '0' || c > '9'){
throw new InputMismatchException ();
}
m /= 10;
res += (c - '0') * m;
c = read ();
}
}
return res * sgn;
}
public boolean isExhausted(){
int value;
while (isSpaceChar (value = peek ()) && value != -1)
read ();
return value == -1;
}
public String next(){
return nextString ();
}
public SpaceCharFilter getFilter(){
return filter;
}
public void setFilter(SpaceCharFilter filter){
this.filter = filter;
}
public interface SpaceCharFilter{
public boolean isSpaceChar(int ch);
}
}
class Pair implements Comparable{
public int a;
public int b;
public Pair(){
this.a = 0;
this.b = 0;
}
public Pair(int a,int b){
this.a = a;
this.b = b;
}
public int compareTo(Pair p){
if(this.a == p.a){
return this.b - p.b;
}
return this.a - p.a;
}
@Override
public String toString(){
return "a = " + this.a + " b = " + this.b;
}
}