Guest User

LVADER

a guest
Feb 16th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.91 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. /**
  6.  * Created by bugkiller on 16/02/18.
  7.  */
  8.  
  9. class LVADER {
  10.     static final int MAX = 100001;
  11.     static final int P = 1000000007;
  12.     static long factorial[] = new long[MAX];
  13.  
  14.     public static void main(String[] args) throws IOException {
  15.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  16.         int t, x1, y1, x2, y2;
  17.         String[] s;
  18.         t = Integer.parseInt(br.readLine());
  19.         fillFactorial();
  20.         while (t-- > 0) {
  21.             s = br.readLine().split("\\s");
  22.             x1 = Integer.parseInt(s[0]);
  23.             y1 = Integer.parseInt(s[1]);
  24.             x2 = Integer.parseInt(s[2]);
  25.             y2 = Integer.parseInt(s[3]);
  26.             System.out.println(solve(x1, y1, x2, y2));
  27.         }
  28.     }
  29.  
  30.     private static long solve(int x1, int y1, int x2, int y2) {
  31.         return totalPaths(x2 - x1, y2 - y1);
  32.     }
  33.  
  34.     private static long totalPaths(int m, int n) {
  35.         int k = Integer.min(m, n);
  36.         long ans = 0;
  37.         for (int i = 0; i <= k; i++) {
  38.             int x = m + n - i;
  39.             long tempAns = (nCR(x, m) * nCR(m, i)) % P;
  40.             ans = (ans + tempAns) % P;
  41.         }
  42.         return ans;
  43.     }
  44.  
  45.     static long nCR(int n, int r) {
  46.         return (((factorial[n] * pow(factorial[r], P - 2)) % P) * pow(factorial[n - r], P - 2)) % P;
  47.     }
  48.  
  49.     public static long pow(long a, long n) {
  50.         if (n > 0) {
  51.             long temp = pow(a, n / 2);
  52.             temp = (temp * temp) % P;
  53.             if ((n & 1) == 1) {
  54.                 temp = (temp * a) % P;
  55.             }
  56.             return temp;
  57.         }
  58.         return 1;
  59.     }
  60.  
  61.     private static void fillFactorial() {
  62.         factorial[0] = 1;
  63.         for (int i = 1; i < MAX; i++) {
  64.             factorial[i] = (factorial[i - 1] * i) % P;
  65.         }
  66.     }
  67.  
  68.  
  69.  
  70. }
Add Comment
Please, Sign In to add comment