import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { new Main().run(); } final int MAX=2100000; long[] fac=new long[MAX]; long[] ifac=new long[MAX]; long[] inv=new long[MAX]; final long MOD=(long)1e9+7; { fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1; for (int i=2;i Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} }