哈哈哈，简单polya，公式自己推导。

不过这题需要用到大数，很久没写Java，调了好久。

import java.math.*;
import java.util.*;
import java.io.*;
public class Main{
	public static void main(String args[]){
		Scanner cin=new Scanner(System.in);
		int n;
		BigInteger c;
		while(cin.hasNextInt())
		{
			BigInteger ans=BigInteger.valueOf(0),tmp;
			n=cin.nextInt();
			c=cin.nextBigInteger();
			int k=n%2;						//奇数的话，在中间有个不动点
			ans=ans.add(c.pow(n*n));		//0度
			ans=ans.add(c.pow((n*n-k)/4+k));  //90度
			ans=ans.add(c.pow((n*n-k)/2+k));  //180
			ans=ans.add(c.pow((n*n-k)/4+k));  //270
	//		System.out.println(ans);
			if(n%2==0){
				tmp=c.pow(n*n/2);
				ans=ans.add(tmp.multiply(BigInteger.valueOf(2)));
				tmp=c.pow(n*(n-1)/2+n);
				ans=ans.add(tmp.multiply(BigInteger.valueOf(2)));

			}
			else{
				tmp=c.pow(n*(n-1)/2+n);
				ans=ans.add(tmp.multiply(BigInteger.valueOf(4)));
			}
			ans=ans.divide(BigInteger.valueOf(8));
			System.out.println(ans);
		}
	}
}