#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

const int q = 1000000000;

struct tree {
  int x,y;
  int v[11],s[11];
  tree *l,*r;
};

typedef tree * link;

tree data[100000];
int cnt = 0;
link root;

void print(tree *root)
{
  if (root == NULL)
  {
    printf("NULL\n");
    return;
  }
  printf("X %d Y %d\n",root->x,root->y);
  for (int i = 1; i < 11;i++)
    printf("V[%d] = %d ",i,root->v[i]);
  printf("\n");
  for (int i = 1; i < 11;i++)
    printf("S[%d] = %d ",i,root->s[i]);
  printf("\n");
  printf("%d's LEFT\n",root->x);
  print(root->l);
  printf("%d's RIGHT\n",root->x);
  print(root->r);
  printf("X %d Y %d END \n",root->x,root->y);
}

int sum(link root,int k)
{
  return !root ? 0 : root->s[k];
}
void update(link root)
{
  if (!root)
    return;
  for (int i = 1; i < 11;i++)
    root->s[i] = ((sum(root->l,i) + sum(root->r,i)) %q + root->v[i]) % q;
}
void split(link root, link &l, link &r, int x)
{
  if (!root)
    l = r = NULL;
  else if (root->x > x)
  {
    split(root->l,l,root->l,x);
    r = root;
  }
  else
  {
    split(root->r,root->r,r,x);
    l = root;
  }
  update(l);
  update(r);
}
void merge(link &root, link l, link r)
{
  if (!l || !r)
    root = l ? l : r;
  else if (l->y < r->y)
  {
    merge(l->r,l->r,r);
    root = l;
  }
  else
  {
    merge(r->l,l,r->l);
    root = r;
  }
  update(root);
}
link make(int x,int y )
{
  link a;
//  a = new tree;
  a = &data[cnt++];
  a->x = x;
  a->l = a->r = NULL;
  a->y = y;
  a->v[1] = a->s[1] = 1;
  for (int i = 2;i < 11;i++)
    a->v[i] = a->s[i] = 0;
  return a;
}
void add(link &root, link a  )
{
  if (root == NULL)
    root = a;
  else if (root->y > a->y)
  {
    link l,r;
    split(root,l,r,a->x);
    a->l = l;
    a->r = r;
    root = a;
  }
  else if (root->x > a->x)
    add(root->l,a);
  else
    add(root->r,a);
  update(root);
}
void tadd(int x)
{

  link a = make(x,rand() << 16 + rand());
  link l,r;
  split(root,l,r,x);
  for (int i = 2; i < 11;i++)
    a->v[i] = a->s[i] = (a->v[i] + sum(r,i - 1)) % q;
  //merge(l,l,a);
  merge(root,l,r);
  add(root,a);
}
int height(link root,int h)
{
  if (!root)
    return h;
  else
    return max(h,max(height(root->l,h + 1),height(root->r,h + 1)));
}
int main()
{
  #ifndef ONLINE_JUDGE
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
  #endif
  srand(time(NULL));
  root = NULL;
  int n,k;
  scanf("%d %d",&n,&k);
  for (int i = 0;i < n  ;i++)
  {

    int a;
    scanf("%d",&a);
    tadd(a);

  }
  printf("%d\n",sum(root,k));
  return 0;
}