板子

package test;
//package test;
import java.util.*;

public class Main {
 static int N = 100010;
 static int[] e = new int[N * 2];
 static int[] ne = new int[N * 2];
 static int[] h = new int[N];
 static int idx = 0;
 static int n, m, q;
 static long cnt = 0;
 static int[][] chess = new int[5][5];
 static void add(int a, int b) {
     e[idx] = b;
     ne[idx] = h[a];
     h[a] = idx++;
 }

 public static void main(String[] args) {
//     Scanner sc = new Scanner(System.in);
//     n = sc.nextInt();
	 System.out.println(ksm(2,2,1003));
     
     

 }
 private static int ksm(int a, int k, int p) {
	    long res = 1L;
	    long t = a % p;
	    while (k > 0) {
	        if ((k & 1) == 1) {
	            res = (res * t) % p;
	        }
	        t = (t * t) % p;
	        k >>= 1;
	    }
	    return (int)res;
	}
private static void dfs(int num, int w, int b) {
	if(num == 25) {
		if(check()) {
			cnt++;
		}
		return;
	}
	int x = num/5, y = num%5;
	if(w<13) {
		chess[x][y] = 0;
		dfs(num+1,w+1,b);
	}
	if(b<12) {
		chess[x][y] = 1;
		dfs(num+1,w,b+1);
	}
	
}

private static boolean check() {
	for(int i = 0; i < 5; i ++ ) {
		int x = 0, y = 0;
		for(int j = 0; j < 5; j ++ ) {
			x += chess[i][j];
			y += chess[j][i];
		}
		if(x==0||x==5)return false;
		if(y==0||y==5)return false;
	}
	int p = 0, q = 0;
	for(int i = 0; i < 5; i ++ ) {
		p += chess[i][i];
		q += chess[i][4-i];
	}
	if(p==0||p==5)return false;
	if(q==0||q==5)return false;
	return true;
}

private static int bfs(int x, int y) {
     boolean[] st = new boolean[N];
     Queue<Pair> q = new LinkedList<>();
     q.offer(new Pair(x, 0));
     st[x] = true;
     int cnt = 1;
     while(!q.isEmpty()) {
    	 Pair ed = q.poll();
    	 int xx  = ed.x;
    	 int yy = ed.y;
    	 if(yy >= y)continue;
    	 
    	 for(int i = h[xx]; i != -1; i = ne[i]) {
    		 int t = e[i];
    		 if(!st[t]) {
    			 st[t] = true;
    			 cnt++;
    			 q.offer(new Pair(t, yy+1));
    		 }
    	 }
     }
     	return cnt;
 }

 static class Pair {
     int x, y;

     public Pair(int x, int y) {
         this.x = x;
         this.y = y;
     }
 }
}