fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     static final int MAX = 100000;
  5.     static final int MOD = 1_000_000_007;
  6.     static long[] factorial = new long[MAX + 1];
  7.     static long[] invFactorial = new long[MAX + 1];
  8.  
  9.     static long modPower(long base, long exp) {
  10.         long result = 1;
  11.         while (exp > 0) {
  12.             if ((exp & 1) == 1) {
  13.                 result = (result * base) % MOD;
  14.             }
  15.             base = (base * base) % MOD;
  16.             exp >>= 1;
  17.         }
  18.         return result;
  19.     }
  20.  
  21.     static void prepareFactorials() {
  22.         factorial[0] = invFactorial[0] = 1;
  23.         for (int i = 1; i <= MAX; i++) {
  24.             factorial[i] = (factorial[i - 1] * i) % MOD;
  25.         }
  26.  
  27.         invFactorial[MAX] = modPower(factorial[MAX], MOD - 2);
  28.         for (int i = MAX - 1; i >= 1; i--) {
  29.             invFactorial[i] = (invFactorial[i + 1] * (i + 1)) % MOD;
  30.         }
  31.     }
  32.  
  33.     static long nCr(int n, int r) {
  34.         if (r < 0 || r > n) return 0;
  35.         return factorial[n] * invFactorial[r] % MOD * invFactorial[n - r] % MOD;
  36.     }
  37.  
  38.     public static void main(String[] args) {
  39.         Scanner sc = new Scanner(System.in);
  40.  
  41.         prepareFactorials();
  42.  
  43.         int testCases = sc.nextInt();
  44.         while (testCases-- > 0) {
  45.             int n = sc.nextInt();
  46.             int r = sc.nextInt();
  47.             System.out.println(nCr(n, r));
  48.         }
  49.  
  50.         sc.close();
  51.     }
  52. }
  53.  
Success #stdin #stdout 0.19s 58644KB
comments (?)
stdin
copy 
2
15 2 
15 3
stdout
copy 
105
455
https://ideone.com/tHq5L2
language:
Java (HotSpot 12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!