DMOPC '18 Contest 2 P5 - Another Sequence Problem

View as PDF

Submit solution


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 N non-negative integers are such that each element is a member of the set {a_1, a_2, \ldots a_K} and whose sum is at most M?

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

Can you help Bob solve his warm up problem?

Constraints

For all subtasks, 0 \leq a_k \leq M.
The a_i's are guaranteed to be pairwise distinct.

Subtask 1 [20%]

1 \leq N, M, K \leq 500

Subtask 2 [20%]

a_k = k-1 for all 1\le k\le K
K = M
1 \leq N \leq 10^{18}
1 \leq M, K \leq 2\,500

Subtask 3 [20%]

1 \leq N \leq 10^{18}
1 \leq M, K\leq 500

Subtask 4 [40%]

1 \leq N \leq 10^{18}
1 \leq M, K \leq 2\,500

Input Specification

The first line of input will contain three space separated integers, N, M, and K.
The second line of input will contain K space-separated integers, a_1, a_2, \ldots, a_K.

Output Specification

The number of sequences that satisfy the given conditions, modulo 10^9 + 7.

Sample Input

2 3 4
1 3 2 0

Sample Output

10

Explanation for Sample

The possible sequences are: [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], and [3, 0].


Comments

There are no comments at the moment.