All Tracks Math Combinatorics Inclusion-Exclusion Problem

Divisible Digits
Tag(s):

Hard

Problem
Editorial
Analytics

You are given n numbers x1,x2,...,xn and a prime number P. Count the number of tuples (y1,...,yn) with 0 ≤ yixi and $$ \displaystyle\binom{y_1+y_2+\ldots+y_n}{y_1,y_2,\ldots,y_n}$$ divisible by P. (Multinomial coefficents)

Since this number can get very large, return the count modulo 10^9+7.

Input format:

The first line of input will contain two integers n, P. The second line of input will contain n integers. The i-th integer on this line is xi.

Output format:

A single integer, the number of tuples modulo 10^9+7.

Constraint:

For all subtasks:
P is prime
1≤ xi
2 ≤ P

Subtask 1 (29 pts):
n = 2
xi ≤ 100
P ≤ 50

Subtask 2 (27 pts):
n ≤ 11
xi ≤ 1,000,000,000
P ≤ 100

Subtask 3 (23 pts):
n = 2
xi ≤ 1,000,000,000
P ≤ 1,000,000

Subtask 4 (21 pts):
n ≤ 11
xi ≤ 1,000,000,000
P ≤ 1,000,000

SAMPLE INPUT
4 3
1 3 2 4
SAMPLE OUTPUT
76
Explanation

We want to find the number of 4-tuples where the first element is between 0 and 1, the second is between 0 and 3, the third is between 0 and 2, and the last is between 0 and 4 such that the multinomial coefficient is divisible by 3. Some examples of tuples that satisfy these constraints are (0,0,1,2), (1,1,1,0), (1,3,2,4).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications