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 *a*<sub class="lower-index">*i*</sub> bugs in every line of code that he writes. 

Let's call a sequence of non-negative integers *v*<sub class="lower-index">1</sub>, *v*<sub class="lower-index">2</sub>, ..., *v*<sub class="lower-index">*n*</sub> a plan, if *v*<sub class="lower-index">1</sub> + *v*<sub class="lower-index">2</sub> + ... + *v*<sub class="lower-index">*n*</sub> = *m*. The programmers follow the plan like that: in the beginning the first programmer writes the first *v*<sub class="lower-index">1</sub> lines of the given task, then the second programmer writes *v*<sub class="lower-index">2</sub> 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*.
The first line contains four integers *n*, *m*, *b*, *mod* (1 ≤ *n*, *m* ≤ 500, 0 ≤ *b* ≤ 500; 1 ≤ *mod* ≤ 10<sup class="upper-index">9</sup> + 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 *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 500) — the number of bugs per line for each programmer.
#include <vector>
#include <unordered_map>
#include <sstream>
#include <unordered_set>
#include <map>
#include <set>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include<stdio.h>
#include <math.h>
#include <iostream>
#include <cstring>
#include <functional>
#include <deque>
using  namespace  std;
typedef long long ll;
typedef unsigned  long long ull;
template <class T>
vector<int> kmp_get_next(T &s){
    int n=s.size();
    vector<int> next(n);
    next[0]=-1;
    for(int i=1;i<n;i++){
        int j=next[i-1];
        while (j!=-1&&s[j]!=s[i-1]){
            j=next[j];
        }
        next[i]=j+1;
    }
    return next;
}
vector<string> get_words_list(string &s){
    s.push_back(' ');
    string cur="";
    vector<string> ans;
    for(int i=0;i<s.size();i++)
        if(s[i]==' '){
            if(cur.size()!=0) ans.push_back(cur);
            cur="";
        }else cur.push_back(s[i]);
    s.pop_back();
    return ans;
}
template <class T> class FenwickTree {
    int limit;
    vector<T> arr;
    //树状数组是从1开始储存的，而不是0
    inline int lowbit(int x) { return x & (-x); }

public:
    FenwickTree(int limit=1) {
        this->limit = limit;
        arr = vector<T>(limit + 1);
    }
    void resize(int limit){
        this->limit = limit;
        arr.resize(limit+1);
    }
    inline void update(int idx, T delta) {
        for (; idx <= limit; idx += lowbit(idx))
            arr[idx] += delta;
    }

    inline T query(int idx) {   //sum->[1,idx]
        T ans = 0;
        for (; idx > 0; idx -= lowbit(idx))
            ans += arr[idx];
        return ans;
    }
};

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        for(int i=0;i<_n;i++)
            parent[i]=i;
    }

    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }

    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
    bool disconnected(int x) {
        parent[x] = x;
        return true;
    }
};
typedef long long ll;
struct ChthollyTree{
    struct node
    {
        ll l, r;
        mutable ll v;
        node(ll l, ll r, ll v) : l(l), r(r), v(v) {}
        bool operator<(const node &o) const { return l < o.l; }
    };
    set<node> tree;
    void insert(ll l,ll r,ll v){
        tree.insert({l,r,v});
    }
    auto split(ll pos)
    {
        auto it = tree.lower_bound(node(pos, 0, 0));
        if (it != tree.end() && it->l == pos)
            return it;
        it--;
        ll l = it->l, r = it->r, v = it->v;
        tree.erase(it);
        tree.insert(node(l, pos - 1, v));
        return tree.insert(node(pos, r, v)).first;
    }
    ll get_sum(ll l, ll r)
    {
        long long ans=0;
        auto end = split(r + 1), begin = split(l),it = begin;
        for(;it!=end;it++)
            ans+=it->v*(it->r-it->l+1);
        return ans;
    }
    void assign(ll l, ll r, ll v)
    {
        auto end = split(r + 1), begin = split(l);
        tree.erase(begin, end);
        tree.insert(node(l, r, v));
    }
    void add(ll l, ll r, ll v)
    {
        auto end = split(r + 1);
        for (auto it = split(l); it != end; it++)
            it->v += v;
    }
    ll kth(ll l, ll r, ll k)
    {
        auto end = split(r + 1);
        vector<pair<ll, ll>> v;
        for (auto it = split(l); it != end; it++)
            v.push_back(make_pair(it->v, it->r - it->l + 1));
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++)
        {
            k -= v[i].second;
            if (k <= 0)
                return v[i].first;
        }
        return 0;
    }
};





//namespace OY {
//    template <typename _Tp, int batch = 1 << 15>
//    struct MemoryPool {
//        static inline std::vector<_Tp *> s_pool;
//        static inline std::vector<_Tp *> s_gc;
//        static inline _Tp *s_cursor = nullptr;
//        static inline _Tp *s_end = nullptr;
//        static void _reserve(int __count = batch) {
//            s_pool.push_back((_Tp *)malloc(__count * sizeof(_Tp)));
//            s_cursor = s_pool.back();
//            s_end = s_cursor + __count;
//        }
//        static void *operator new(size_t) {
//            if (s_gc.size()) {
//                auto it = s_gc.back();
//                s_gc.pop_back();
//                return it;
//            } else if (s_cursor == s_end)
//                _reserve();
//            return s_cursor++;
//        }
//        static void operator delete(void *it) { s_gc.push_back((_Tp *)it); }
//        static void recycle(_Tp *it) { s_gc.push_back(it); }
//    };
//}
//
//class SegmentTree6
//{
//public:
//    struct Node:OY::MemoryPool<Node>{
//        Node *left,*right;
//        int start, end;
//        int info;     //存的就已经是区间正确的值（已经包括了标记的影响）
//        int tag;      //是需要往left,right继续传递的标记
//        Node(int a, int b):start(a),end(b),info(0),tag(0),left(NULL),right(NULL){}
//    };
//    Node *root;
//    SegmentTree6(int a,int b){
//        root=new Node(a,b);
//        //build(root,a,b);
//    }
//    void build(Node* node, int a, int b)  // init for range [a,b]
//    {
//        if (a==b)
//        {
//            node->info = 0;
//            return;
//        }
//        int mid = (a+b)>>1;
//
//        node->left = new Node(a, mid);
//        node->right = new Node(mid+1, b);
//
//        build(node->left, a, mid);
//        build(node->right, mid+1, b);
//        pushUp(node);           // write your own logic
//    }
//    void pushUp(Node *node){
//        node->info = max(node->left->info,node->right->info) ;  // write your own logic
//    }
//    void updateRangeBy(Node* node, int a, int b, int val)
//    {
//        if (a <= node->start && node->end <=b)
//        {
//            // write your own logic
//            node->info = val;
//            node->tag = val;
//            return;
//        }
//
//        pushDown(node);          // write your own logic
//        int mid=(node->start+node->end)>>1;
//        if(a<=mid) updateRangeBy(node->left, a, b, val);
//        if(b>mid) updateRangeBy(node->right, a, b, val);
//
//        pushUp(node);               // write your own logic
//    }
//
//    int len(Node* node)
//    {
//        return node->end - node->start + 1;
//    }
//
//    void pushDown(Node* node)
//    {
//        int mid=(node->start+node->end)>>1;
//        if(!node->left) node->left=new Node(node->start,mid);
//        if(!node->right) node->right=new Node(mid+1,node->end);
//        if (node->tag!=0)
//        {
//            node->left->info =  node->tag;
//            node->left->tag = node->tag;
//            node->right->info =  node->tag;
//            node->right->tag = node->tag;
//            node->tag = 0;
//        }
//    }
//    int queryRange(Node* node, int a, int b)
//    {
//        if (a <= node->start && b>=node->end)
//        {
//            return node->info;  // write your own logic
//        }
//        pushDown(node);          // write your own logic
//        int mid=(node->start+node->end)>>1;
//        int ans=0;
//        if(a<=mid) ans= max(queryRange(node->left, a, b),ans);
//        if(b>mid)  ans=max(queryRange(node->right, a, b),ans);
//        return ans;   // write your own logic
//    }
//};
//
//
//class Solution {
//public:
//
//    int lengthOfLIS(vector<int>& nums,int k) {
//        int n=nums.size();
//        int m= *max_element(nums.begin(),nums.end());
//        SegmentTree6 tree=SegmentTree6(1,m);
//        tree.updateRangeBy(tree.root,1,1,1);
//        int ans=1;
//        for(auto &x:nums){
//            if(x==1) continue;
//            int v=tree.queryRange(tree.root, max(x-k,1), max(x-1,1));
//            int cur=tree.queryRange(tree.root,x,x);
//            if(cur<v+1){
//                tree.updateRangeBy(tree.root,x,x,v+1);
//            }
//            ans= max(ans,v+1);
//        }
//        return ans;
//    }
//};


int f[502][501][501];
int a[501];
int main() {
    //freopen("input.txt", "r", stdin);
//	  freopen("output.txt", "w", stdout);
//    int t;
//    cin>>t;
    ios::sync_with_stdio(false);

//    int t;
//    cin>>t;
//    getchar();
//    while (t--){
//        string line;
//        getline(cin, line);
//        stringstream ss(line);
//        vector<int> nums;
//        int x;
//        while (ss >> x)
//            nums.push_back(x);
//        for(auto y:nums) cout<<y<<" ";
//        cout<<endl;
//    }
    int n,m,b,mod;
    cin>>n>>m>>b>>mod;
    for(int i=0;i<n;i++) cin>>a[i];
    f[0][0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=b;k++){
                if(!f[i][j][k]) continue;
                if(i!=0&&j+1<=m&&k+a[i-1]<=b) f[i][j+1][k+a[i-1]]=(f[i][j+1][k+a[i-1]]+f[i][j][k])%mod;
                f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;
            }
    int ans=0;
    for(int k=0;k<=b;k++) ans=(ans+f[n+1][m][k])%mod;
    cout<<ans<<endl;
    return 0;
}