oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

balloons Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

balloons.html

Problem Description

Coco the Monkey is performing at a circus and is currently handing out colourful balloons to the audience.

Coco the Monkey has balloons of N colours numbered from 1 to N. Coco the Monkey has Ai balloons of the ith colour. Each person in the audience gets exactly K balloons.

Damian and Fan Pu have come to see Coco the Monkey perform at the circus. As they watch Coco the Monkey distribute balloons, Damian wonders, how many different possible combinations of colours of balloons Coco the Monkey can give someone in the audience? Two combinations are considered distinct if the number of balloons present in one combination and in another combination is different for a certain colour.

Damian asks Fan Pu his question, but Fan Pu wants to watch the performance. As such, can you help Damian calculate the answer, modulo 109 + 7?

Input

The first line of input will contain two integers, N and K.

The following line of input will contain N space separated integers, Ai.

Output

Output a single integer, the number of distinct combinations, modulo 109 + 7.

Limits

Subtask 1 (14%): 1 ≤ N ≤ 3. 1 ≤ K ≤ 1500. 1 ≤ Ai ≤ 1000.

Subtask 2 (29%): 1 ≤ N ≤ 20. 1 ≤ K ≤ 104. 1 ≤ Ai ≤ 1000.

Subtask 3 (57%): 1 ≤ N ≤ 20. 1 ≤ K ≤ 1014. 1 ≤ Ai ≤ 1012.

Subtask 4 (0%): Sample Testcases

Sample Testcase 1

Input

3 5
1 3 2

Output

3

Tags

Math

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114301s64MBMinimum
229601s64MBMinimum
3571101s64MBMinimum
4011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o balloons -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.