import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.OutputStream; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.StringTokenizer; public class Main { static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input) { reader = new BufferedReader( new InputStreamReader(input) ); tokenizer = new StringTokenizer(""); } static String next() throws IOException { while ( ! tokenizer.hasMoreTokens() ) { tokenizer = new StringTokenizer(reader.readLine() ); } return tokenizer.nextToken(); } static long nextInt() throws IOException { return Long.parseLong( next() ); } static PrintWriter writer; static void outit(OutputStream outputStream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); } static void print(Object...objects) { for (int i = 0; i < objects.length; i++) { if (i != 0) writer.print(' '); writer.print(objects[i]); } } static void println(Object...objects) { print(objects); writer.println(); } static void close() { writer.close(); } static void flush() { writer.flush(); } static ArrayList> sieve ; static long [] mob ; public static void main(String [] args) throws IOException { init(System.in) ; outit(System.out) ; // int t = (int)nextInt() ; // for(int i =0 ; i 0) { if(b%2 == 1) { x=(x*y); if(x>MOD) x%=MOD; } y = (y*y); if(y>MOD) y%=MOD; b /= 2; } return x; } public static long InverseEuler(long n, long MOD) { return pow(n,MOD-2,MOD); } static void updateBIT(long[] arr, int pos, long val) { int len = arr.length; for (; pos < len; pos |= (pos + 1)) arr[pos] =(arr[pos]+ val)%mod; } static long query(long[] arr, int pos) { long sum = 0; for (; pos >= 0; pos = (pos & (pos + 1)) - 1) sum = (sum+ arr[pos])%mod; return sum; } static void print_BIT(long []BIT,int n) { for(int i = 0 ; i