/*

设dp[i]表示前i个做划分满足条件的方案数

有一个显然的转移方程dp[i]=sigma(dp[j])  t<=j<=i-1

其中t是满足mex(a[t..i-1])<=k的最小的t

然后我们现在是想得到，对于每个位置这个t是多少，如果知道了这个，就可以很容易的转移了

首先，考虑，如果k>n，那么不管怎么选，都是会满足条件的啊！（就算把所有的数都选出来，mex也就是k吧）

所以对于k>n，直接输出2^(n-1)
当然k=0的时候特判一下，这样每个i对应的t都是存在的，至少有一个i

现在考虑k<=n的情况，直接用一个multiset记录[1,k]里的数的出现情况

首先，把[0,k]全部都放进multiset，遇到一个新的数，就erase，查询集合里最小的数就是mex 

假设现在想得到第i个位置的t，上次求得的i-1对应的t是t'

那么如果a[i]已经在集合中被删去了，那这次对应的肯定还是t'

如果a[i]没有从集合中删去，就把a[i]从集合中删去（当然，如果a[i]>k直接不用管）

考虑到随着i的增大，t肯定是往右走的

如果删去以后集合是空集了，那t'就需要右移了，直到出现一个[0,k]之间的，并且在a[t+1..i]没有出现过的数

是否出现过，只需要记一个右边第一个跟它相等的数就可以了

*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int a[maxn];

int t[maxn];

int e[maxn];

long long dp[maxn];

long long predp[maxn];

pair<int,int> p[maxn];

set<int> S;

const long long md=;

long long fp(long long a,long long k)

{

    long long res=;

    a%=md;

    while(k)

    {

        if(k&)res=res*a%md;

        a=a*a%md;

        k>>=;

    }

    return res;

}

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

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

    if (k>n)

    {

        printf("%lld",fp(,n-));

        return ;

    }

    if (k==)

    {

        bool yl=false;

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

        {

            if (a[i]==)

            {

                yl=true;

                break;

            }

        }

        if (yl) printf("0\n");

        else printf("%lld",fp(,n-));

        return ;

    }

    S.clear();

    for (int i=;i<=k;i++) S.insert(i);

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

    {

        p[i].first=a[i];

        p[i].second=i;

    }

    sort(p+,p++n);

    p[n+].first=-;

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

    {

        if (p[i+].first==p[i].first) e[p[i].second]=p[i+].second;

        else e[p[i].second]=-;

    }

    int now=;

    t[]=;

    if (a[]<=k) S.erase(a[]);

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

    {

        if (a[i]>k || !S.count(a[i])) t[i]=t[i-];

        else

        {

            S.erase(a[i]);

            while (S.empty())

            {

                if (a[now]<=k && (e[now]==-||e[now]>i))

                {

                    S.insert(a[now]);

                }

                now++;

            }

            t[i]=now;

        }

    }

    dp[]=;

    predp[]=;

    predp[]=;

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

    {

        // dp[t[i]-1]...dp[i-1]

        dp[i]=((predp[i]-predp[t[i]-])%md+md)%md;

        predp[i+]=(predp[i]+dp[i])%md;

    }

    printf("%lld\n",dp[n]);

    return ;

}