import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) throws FileNotFoundException { long t = System.currentTimeMillis(); new Main().run(); System.err.println(System.currentTimeMillis() - t); } Scanner sc = new Scanner(); final long MOD=(long)1e9+7; long[] fac=new long[500000]; long[] ifac=new long[500000]; long[] inv=new long[500000]; { fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1; for(int i=2;i