543_A. Writing Code_36750
Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly ai bugs in every line of code that he writes. 

Let's call a sequence of non-negative integers v1, v2, ..., vn a plan, if v1 + v2 + ... + vn = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v1 lines of the given task, then the second programmer writes v2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let's call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.

Input

The first line contains four integers n, m, b, mod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — the number of programmers, the number of lines of code in the task, the maximum total number of bugs respectively and the modulo you should use when printing the answer.

The next line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 500) — the number of bugs per line for each programmer.

Output

Print a single integer — the answer to the problem modulo mod.

Examples

Input

3 3 3 100
1 1 1


Output

10


Input

3 6 5 1000000007
1 2 3


Output

0


Input

3 5 6 11
1 2 1


Output

0
"""
________        _____________              ______
___  __ \____  ____  __ \__(_)__   _______ ___  /
__  /_/ /_  / / /_  /_/ /_  /__ | / /  __ `/_  /
_  ____/_  /_/ /_  _, _/_  / __ |/ // /_/ /_  /
/_/     _\__, / /_/ |_| /_/  _____/ \__,_/ /_/
        /____/

https://github.com/Cheran-Senthil/PyRival
Copyright (c) 2018 Cheran Senthilkumar
"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
import sys
from atexit import register
from bisect import bisect_left, bisect_right

# import random
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    from io import BytesIO as stream
    # from fractions import Fraction
    # from fractions import gcd
    # from cPickle import dumps
    # from Queue import PriorityQueue, Queue
else:
    from io import StringIO as stream
    # from functools import reduce
    # from fractions import Fraction
    # from math import gcd
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        def items(self):
            return dict.iteritems(self)

        def keys(self):
            return dict.iterkeys(self)

        def values(self):
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """
    Sets whether the standard Python streams are allowed to buffer their I/O.

    Parameters
    ----------
    sync : bool, optional
        The new synchronization setting. Default is True.
    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def main():
    n, m, b, mod = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    dp = [[0] * (b + 1) if i > 0 else [1] * (b + 1) for i in range(m + 1)]

    for i in range(n):
        for j in range(1, m + 1):
            for k in range(a[i], b + 1):
                dp[j][k] = (dp[j - 1][k - a[i]] + dp[j][k]) % mod

    print(dp[m][b])


if __name__ == '__main__':
    sys.setrecursionlimit(10000)
    sync_with_stdio(False)
    main()

3 6 5 1000000007
1 2 3
 3 3 3 100
1 1 1
 3 5 6 11
1 2 1
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 1 1 1 1
2
 2 3 3 1000
1 2
 1 1 0 1000
0
 1 5 1 10
1
 29 157 50 1
3 0 0 3 1 1 2 0 4 4 1 2 2 1 0 0 2 0 3 2 2 3 3 1 4 1 1 4 1
 2 500 50 10000
0 50
 1 1 1 1
0
 1 5 5 1000
1
 1 4 25 1000
6
 10 9 20 48620
1 1 1 1 1 1 1 1 2 2
 21 63 40 1009
4 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 1 5 5 1000
500
 2 500 250 100
100 200
 3 10 10 150691913
8 7 10
 100 500 500 1000000007
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 31 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 7 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 82 22 27 6 52 21 1 5 74 96 77 76 24 4 46 30 36 97 60
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 98 105 0 120 93 78 61 17 84 48 42 106 63 103 7 59 90 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 39 11 37 18 10 2 9 38 17 36 49 1 32 6 20 5 37 18 31 44 1 36 24 35 13 35 8 10 26 45 43 28 38 22
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 1 2 1 1
2
 1 1 1 1000
0
 21 63 40 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 100 261 500 1000000007
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 7 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 82 22 27 6 52 21 1 5 74 96 77 76 24 4 46 30 36 97 60
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 98 105 0 120 93 78 61 17 84 48 42 106 63 103 7 59 150 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 39 11 37 18 10 2 9 38 17 36 49 1 32 6 20 5 37 14 31 44 1 36 24 35 13 35 8 10 26 45 43 28 38 22
 3 5 5 11
1 2 1
 21 44 40 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 7 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 151 22 27 6 52 21 1 5 74 96 77 76 24 4 46 30 36 97 60
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 14 105 0 120 93 78 61 17 84 48 42 106 63 103 7 59 150 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 21 35 40 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 2 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 151 22 27 6 52 21 1 5 74 96 77 76 24 4 46 30 36 97 60
 21 35 20 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 2 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 151 28 27 6 52 21 1 5 74 96 77 76 24 4 46 30 36 97 60
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 39 11 37 18 10 2 9 38 17 36 49 1 32 1 40 5 37 14 31 44 1 66 24 35 13 35 8 10 26 45 43 28 38 22
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 2 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 21 55 20 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 4 3 0 4 2 4
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 2 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 10 23 87 19 45 94 44 151 28 27 6 52 21 1 4 74 96 77 76 24 4 46 30 36 97 60
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 2 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 2 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 21 55 20 1009
8 4 2 2 4 4 3 2 4 2 0 3 3 4 3 0 3 0 4 2 4
 100 500 499 1000000007
72 20 34 92 65 29 40 41 18 16 86 14 88 37 59 11 39 91 13 43 47 73 80 35 62 12 9 81 55 66 54 2 50 57 8 25 98 58 0 15 93 78 61 17 84 48 42 38 63 68 2 59 90 89 28 49 53 71 51 83 75 67 64 95 70 3 32 85 69 99 33 79 26 56 20 23 87 19 45 94 44 151 28 27 6 52 21 1 4 74 96 77 76 24 4 46 30 36 97 60
 2 6 3 1000
1 2
 29 157 50 1
3 0 0 3 1 1 2 0 4 4 1 2 2 1 0 0 2 0 3 2 2 3 3 0 4 1 1 4 1
 2 500 50 10000
0 84
 1 1 0 1
0
 1 4 7 1000
6
 1 6 5 1000
500
 3 10 10 177552844
8 7 10
 3 6 5 1000000007
1 2 4
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 1 2 1 2
2
 1 1 1 1001
0
 29 157 50 1
3 0 0 3 1 1 2 0 4 4 1 2 2 1 0 0 2 0 3 0 2 3 3 0 4 1 1 4 1
 2 500 50 10001
0 84
 1 4 0 1000
6
 1 6 5 1010
500
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 39 11 37 18 10 2 9 38 17 36 49 1 32 6 20 5 37 14 31 44 1 66 24 35 13 35 8 10 26 45 43 28 38 22
 3 6 0 1000000007
1 2 4
 1 5 5 11
1 2 1
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 1 1 0 1001
0
 1 6 5 1011
500
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 14 105 1 120 93 78 61 17 84 48 42 106 63 103 7 59 150 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 39 11 37 18 10 2 9 38 17 36 49 1 32 6 40 5 37 14 31 44 1 66 24 35 13 35 8 10 26 45 43 28 38 22
 3 6 0 1000000007
1 1 4
 1 5 5 5
1 2 1
 100 100 100 960694994
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1
 1 1 0 1000
1
 1 3 5 1011
500
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 14 105 1 120 93 78 61 17 84 48 42 12 63 103 7 59 150 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 3 6 0 1916151952
1 1 4
 1 5 5 5
1 2 0
 1 2 0 1000
1
 123 432 342 1000000007
72 20 34 115 65 29 114 41 18 16 122 104 88 37 119 11 108 91 13 110 47 73 80 35 62 12 9 116 55 66 54 113 50 57 8 25 14 105 1 120 93 124 61 17 84 48 42 12 63 103 7 59 150 89 28 49 53 71 51 83 75 67 64 95 107 3 32 85 69 99 33 79 109 56 10 23 87 19 121 94 44 82 102 27 112 52 21 1 5 74 117 111 76 24 4 101 30 36 97 60 92 46 22 68 118 58 38 70 39 26 43 77 6 2 40 100 81 96 14 31 15 45 86
 100 500 500 895583345
20 39 5 5 41 47 36 33 34 22 21 33 7 4 15 35 16 37 39 46 27 4 12 35 43 26 23 40 16 50 27 7 49 28 17 28 16 22 18 12 25 34 28 24 10 21 38 10 40 50 35 18 23 38 10 42 22 19 24 45 33 34 50 24 29 36 14 11 37 18 10 2 9 38 17 36 49 1 32 1 40 5 37 14 31 44 1 66 24 35 13 35 8 10 26 45 43 28 38 22
 1 5 5 5
1 3 0
 1 2 0 1001
1

0
 10
 0
 527886216
 0
 1
 1
 0
 0
 2
 0
 1
 1
 0
 1002
 0
 0
 0
 925584498
 416898599
 902925242
 501
 527886216 0 1 693 855003392 636219703 284221765 501 6 417 233589394 31582838 658 346998164 851 29913760 125751 887481717 239 560470608 214606895 902 430031037 0 0 1 0 0 0 0 0 527886216 0 1 0 1 0 0 501 0 1 527886216 1 0 0 501 0 1 527886216 0 0 0 0 1 0 0 125751 1 0