Submission #19560143


Source Code Expand

Copy
import java.io.*;
import java.util.*;

public class Main {
    private static final boolean N_CASE = false;

    private static final int MOD = 1_000_000_007;
    private long add(long a, long b) { return (((a + b) % MOD + MOD) % MOD);}
    private long sub(long a, long b) { return (((a - b) % MOD + MOD) % MOD); }
    private long mul(long a, long b) { return (((a * b) % MOD + MOD) % MOD); }
    private long div(long a, long b) { return (((a * inv(b)) % MOD + MOD) % MOD); }
    private long inv(long a) { return pow(a, MOD - 2); }
    private long pow(long a, int n) {
        long ret = 1;
        while (n > 0) {
            if ((n & 1) > 0) { ret = mul(ret, a); }
            a = mul(a, a);
            n >>= 1;
        }
        return ret;
    }


    private void solve() {
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = sc.nextIntArray(N);

        long S = 0;
        for (int i = 0; i < N; i++) {
            S += A[i];
        }

        if (S > M) {
            out.println(0);
            return;
        }

        long X = M + N;
        long Y = M - S;

        Y = Math.min(Y, X - Y);
        long N1 = 1, N2 = 1;
        for (int i = 1; i <= Y; ++i) {
            N1 = mul(N1, X + 1 - i);
            N2 = mul(N2, i);
        }

        out.println(div(N1, N2));
    }

    private void run() {
        int T = N_CASE ? sc.nextInt() : 1;
        for (int t = 0; t < T; ++t) {
            solve();
        }
    }

    private static MyWriter out;
    private static MyScanner sc;

    private static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        private MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[][] nextIntArray(int n, int m) {
            int[][] a = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    a[i][j] = sc.nextInt();
                }
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }

        long[][] nextLongArray(int n, int m) {
            long[][] a = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    a[i][j] = nextLong();
                }
            }
            return a;
        }

        List<Integer> nextList(int n) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(nextInt());
            }
            return list;
        }

        List<Long> nextLongList(int n) {
            List<Long> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(nextLong());
            }
            return list;
        }

        char[] nextCharArray(int n) {
            return sc.next().toCharArray();
        }

        char[][] nextCharArray(int n, int m) {
            char[][] c = new char[n][m];
            for (int i = 0; i < n; i++) {
                String s = sc.next();
                for (int j = 0; j < m; j++) {
                    c[i][j] = s.charAt(j);
                }
            }
            return c;
        }
    }

    private static class MyWriter extends PrintWriter {
        private MyWriter(OutputStream outputStream) {
            super(outputStream);
        }

        void printArray(int[] a) {
            for (int i = 0; i < a.length; ++i) {
                print(a[i]);
                print(i == a.length - 1 ? '\n' : ' ');
            }
        }

        void printArray(long[] a) {
            for (int i = 0; i < a.length; ++i) {
                print(a[i]);
                print(i == a.length - 1 ? '\n' : ' ');
            }
        }

        void println(int[] a) {
            for (int v : a) {
                println(v);
            }
        }

        void print(List<Integer> list) {
            for (int i = 0; i < list.size(); ++i) {
                print(list.get(i));
                print(i == list.size() - 1 ? '\n' : ' ');
            }
        }

        void println(List<Integer> list) {
            list.forEach(this::println);
        }
    }

    private <T> List<List<T>> createGraph(int n) {
        List<List<T>> g = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            g.add(new ArrayList<>());
        }
        return g;
    }

    private void fill(int[][] a, int value) {
        for (int[] row : a) {
            fill(row, value);
        }
    }

    private void fill(int[] a, int value) {
        Arrays.fill(a, value);
    }

    public static void main(String[] args) {
        out = new MyWriter(new BufferedOutputStream(System.out));
        sc = new MyScanner();
        new Main().run();
        out.close();
    }
}

Submission Info

Submission Time
Task D - Binomial Coefficient is Fun
User zhupeijun
Language Java (OpenJDK 11.0.6)
Score 600
Code Size 5929 Byte
Status AC
Exec Time 140 ms
Memory 33544 KB

Judge Result

Set Name All Sample
Score / Max Score 600 / 600 0 / 0
Status
AC × 72
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_56.txt, testcase_57.txt, testcase_58.txt, testcase_59.txt, testcase_6.txt, testcase_60.txt, testcase_61.txt, testcase_62.txt, testcase_63.txt, testcase_64.txt, testcase_65.txt, testcase_66.txt, testcase_67.txt, testcase_68.txt, testcase_69.txt, testcase_7.txt, testcase_70.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 82 ms 32844 KB
sample_02.txt AC 77 ms 32852 KB
testcase_1.txt AC 75 ms 32204 KB
testcase_10.txt AC 92 ms 33248 KB
testcase_11.txt AC 84 ms 33184 KB
testcase_12.txt AC 84 ms 33220 KB
testcase_13.txt AC 125 ms 33340 KB
testcase_14.txt AC 114 ms 33220 KB
testcase_15.txt AC 129 ms 33292 KB
testcase_16.txt AC 118 ms 33328 KB
testcase_17.txt AC 114 ms 33260 KB
testcase_18.txt AC 121 ms 33448 KB
testcase_19.txt AC 113 ms 33492 KB
testcase_2.txt AC 78 ms 32720 KB
testcase_20.txt AC 125 ms 33412 KB
testcase_21.txt AC 123 ms 33328 KB
testcase_22.txt AC 123 ms 33388 KB
testcase_23.txt AC 118 ms 33292 KB
testcase_24.txt AC 122 ms 33380 KB
testcase_25.txt AC 126 ms 33528 KB
testcase_26.txt AC 117 ms 33328 KB
testcase_27.txt AC 126 ms 33328 KB
testcase_28.txt AC 122 ms 33320 KB
testcase_29.txt AC 119 ms 33276 KB
testcase_3.txt AC 83 ms 32728 KB
testcase_30.txt AC 126 ms 33336 KB
testcase_31.txt AC 114 ms 33348 KB
testcase_32.txt AC 120 ms 33384 KB
testcase_33.txt AC 122 ms 33368 KB
testcase_34.txt AC 118 ms 33436 KB
testcase_35.txt AC 122 ms 33376 KB
testcase_36.txt AC 116 ms 33324 KB
testcase_37.txt AC 115 ms 33180 KB
testcase_38.txt AC 126 ms 33348 KB
testcase_39.txt AC 123 ms 33160 KB
testcase_4.txt AC 76 ms 32796 KB
testcase_40.txt AC 114 ms 33312 KB
testcase_41.txt AC 115 ms 33448 KB
testcase_42.txt AC 110 ms 33544 KB
testcase_43.txt AC 118 ms 33508 KB
testcase_44.txt AC 120 ms 33300 KB
testcase_45.txt AC 112 ms 33320 KB
testcase_46.txt AC 115 ms 33232 KB
testcase_47.txt AC 130 ms 33464 KB
testcase_48.txt AC 116 ms 33304 KB
testcase_49.txt AC 113 ms 33336 KB
testcase_5.txt AC 76 ms 32688 KB
testcase_50.txt AC 123 ms 33368 KB
testcase_51.txt AC 118 ms 33352 KB
testcase_52.txt AC 117 ms 33336 KB
testcase_53.txt AC 113 ms 33308 KB
testcase_54.txt AC 83 ms 33220 KB
testcase_55.txt AC 93 ms 33152 KB
testcase_56.txt AC 89 ms 33048 KB
testcase_57.txt AC 88 ms 33112 KB
testcase_58.txt AC 82 ms 33080 KB
testcase_59.txt AC 92 ms 33308 KB
testcase_6.txt AC 75 ms 32720 KB
testcase_60.txt AC 91 ms 33196 KB
testcase_61.txt AC 85 ms 33036 KB
testcase_62.txt AC 89 ms 33400 KB
testcase_63.txt AC 85 ms 33148 KB
testcase_64.txt AC 81 ms 33092 KB
testcase_65.txt AC 84 ms 33164 KB
testcase_66.txt AC 82 ms 33060 KB
testcase_67.txt AC 80 ms 33072 KB
testcase_68.txt AC 91 ms 33204 KB
testcase_69.txt AC 80 ms 33152 KB
testcase_7.txt AC 89 ms 33188 KB
testcase_70.txt AC 87 ms 33148 KB
testcase_8.txt AC 124 ms 33324 KB
testcase_9.txt AC 140 ms 33344 KB