import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; class Main { public static void main(String[] args) { new Main().run(); } void run() { solve(); } long mod=(long)1e9+7; long pow(long a, long n) { if (n==0) return 1; return pow(a*a%mod,n/2) * (n%2==1?a:1) %mod; } long inv(long a) { return pow(a, mod-2); } long c(int n, int k) { // if (n==k) return 1; if (n<0||k<0||n-k<0) return 0; // return (c(n-1,k)+c(n-1,k-1))%mod; return fac[n]*ifac[k]%mod*ifac[n-k]%mod; } long slow(int H, int W) { long ans=0; for (int i=0;i<=H;++i) { for (int j=0;j<=W;++j) { ans+=pow(2,i*j)*pow(-1,i+j)%mod*c(H,i)%mod*c(W,j)%mod; ans%=mod; } } ans=ans*pow(-1,H+W)%mod; ans=(ans+mod)%mod; return ans; } int MAX=2000000; long[] fac=new long[MAX]; long[] ifac=new long[MAX]; long[] inv=new long[MAX]; { fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1; for (int i=2;i