## DMOPC '18 Contest 2 P5 - Another Sequence Problem

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

Bob is investigating properties of integer sequences in an attempt to solve George's least favourite problem: Maintaining A Sequence!

To help Bob achieve his dreams, George gives Bob a warm up problem:

How many ordered sequences of non-negative integers are such that each element is a member of the set and whose sum is at most ?

Bob points out that this number might be a bit large, so George lets him return the answer modulo .

Can you help Bob solve his warm up problem?

#### Constraints

The 's are guaranteed to be pairwise distinct.

for all

#### Input Specification

The first line of input will contain three space separated integers, , , and .
The second line of input will contain space-separated integers, .

#### Output Specification

The number of sequences that satisfy the given conditions, modulo .

#### Sample Input

2 3 4
1 3 2 0

#### Sample Output

10

#### Explanation for Sample

The possible sequences are: , , , , , , , , , and .