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?
For all subtasks, .
The 's are guaranteed to be pairwise distinct.
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [20%]
Subtask 4 [40%]
The first line of input will contain three space separated integers, , , and .
The second line of input will contain space-separated integers, .
The number of sequences that satisfy the given conditions, modulo .
2 3 4 1 3 2 0
Explanation for Sample
The possible sequences are: , , , , , , , , , and .