経路探索（フェルマーの小定理／数え上げ）

ABC034_C

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.math.*;

public class Main {
	static final long mod = 1000000007;

	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] str = br.readLine().split(" ");
		int w = Integer.parseInt(str[0]) - 1;
		int h = Integer.parseInt(str[1]) - 1;
		long m = pow(w+h);
		long n = (pow(w) * pow(h))%mod;
		//answer : (m * n^(mod-2))%mod
		long s = (m * binpow(n,mod-2))%mod;

		sb.append(s);
		System.out.print(sb);
	}

	public static long pow(int a){
		long p = 1;
		for(int i = a; i > 0; i--){
			p *= i;
			p %= mod;
		}
		return p;
	}

	public static long binpow(long a, long p){
		String str = Long.toBinaryString(p);
		int l = str.length();
		long[] bp = new long[l+1];
		bp[0] = 1;
		bp[1] = a;
		for(int i = 2; i < l+1; i++)
			bp[i] = (bp[i-1] * bp[i-1]) % mod;
		
		long res = 1;
		for(int i = 0; i < l; i++){
			char c = str.charAt(i);
			if(c=='1')
				res = (res * bp[l-i]) % mod;
		}
		return res;
	}
}