#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + ;

int s[];

int nex[][];

int now[];

ll dp[][];

int main()

{

    int n, m, kk;

    while(~scanf("%d%d%d", &n, &m, &kk))

    {

        memset(dp, , sizeof(dp));

        for(int i = ; i <= n; i++) scanf("%lld", &s[i]);

        for(int i = ; i <= kk; i++) now[i] = n + ;

        for(int i = n; i >= ; i--)

        {

            for(int j = ; j <= kk; j++) nex[i][j] = now[j];

            now[s[i]] = i;

        }

        dp[][] = ; //dp[0][0] = 1;

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= m; j++)

            {

                if(!dp[i][j]) continue;

                for(int k = ; k <= kk; k++)

                {

                    int t = nex[i][k];

                    if(t == n + ) continue;

                    if(t - i + j -  > m) continue;

                    (dp[t][t - i + j - ] += dp[i][j]) %= mod;

                }

            }

        }

        ll ans = ;

        for(int i = ; i <= n; i++)

            if(i - n + m >= )

                (ans += dp[i][i - n + m]) %= mod;

        printf("%lld\n",  ans);

    }

    return ;

}