using namespace std;
#include<stdio.h>
#include<fstream>
#define nmax 100005
#define kmax 34

struct nod{int vec,c;nod* next;};
typedef nod* list;
list a[nmax],aux;
struct nod2{int nd;nod2* next;};
typedef nod2* list2;
list2 aa[nmax];

int n,q;
long long sum[nmax][kmax];
char viz[nmax];
int nc[nmax];


int main()
{
/*
FILE *fin=fopen("caravane.in","r"),
     *fout=fopen("caravane.out","w");
     
fscanf(fin,"%d%d",&n,&q);
*/
int i,j,k,cst;
n=100000;
q=32;

for(i=1;i<n;i++)
   {
//   fscanf(fin,"%d%d%d",&j,&k,&cst);
   j=i;
   k=i+1;
   cst=1;
   
   if(a[j]==NULL)
      {
      a[j]=new nod;
      a[j]->next=NULL;
      }
   else
      {
      aux=new nod;
      aux->next=a[j];
      a[j]=aux;
      }
   a[j]->vec=k;
   a[j]->c=cst;
   
   
   if(a[k]==NULL)
      {
      a[k]=new nod;
      a[k]->next=NULL;           
      }
   else
      {
      aux=new nod;
      aux->next=a[k];
      a[k]=aux;                           
      }
   a[k]->vec=j;
   a[k]->c=cst;
   }
  
//BFS
memset(viz,0,sizeof viz);
int li,lf;
li=lf=1;
nc[1]=1;
viz[1]=1;

while(li<=lf)
  {
  aux=a[nc[li]];
  while(aux)
    {
    if(viz[aux->vec]==0)
       {
       nc[++lf]=aux->vec;
       viz[aux->vec]=1;                 
       }        
    aux=aux->next;
    }
  li++;
  }    
  
for(i=1;i<=n;i++)
   for(j=0;j<=k;j++)
        sum[i][j]=11111111111111;

/*  
for(i=1;i<=n;i++)
   {
   aa[i]=new nod2;
   for(j=0;j<=q;j++)
      {
      aa[i]->nd[j]=0;
      sum[i][j]=0;
      }
   aa[i]->nd[0]=1;
   }

int v;
for(i=lf;i;i--)
  {
  viz[nc[i]]=0;
  
  for(aux=a[nc[i]];aux;aux=aux->next)
     if(viz[aux->vec]==0)
        {
        v=aux->vec;
        for(j=1;j<q;j++)
          {
          aa[nc[i]]->nd[j+1]+=aa[v]->nd[j];
          sum[nc[i]][j+1]=sum[v][j] + (long long)aux->c*aa[v]->nd[j];
          }
          
        aa[nc[i]]->nd[1]++;
        sum[nc[i]][1]+=aux->c;        
        }  
  }
  
long long sol=0,x,y,sol2=0;
for(i=1;i<q;i++)
  {
  for(j=1;j<=lf;j++)
   {
   viz[nc[j]]=1;
   
   for(aux=a[nc[j]];aux;aux=aux->next)
    if(viz[aux->vec]==0)
     {
     x=sum[aux->vec][i-1] + (long long)aux->c*aa[aux->vec]->nd[i-1];
     y=sum[nc[j]][q-i] - (sum[aux->vec][q-i-1] + (long long)aux->c*aa[aux->vec]->nd[q-i-1] );
     
     sol+=x* (aa[nc[j]]->nd[i] - aa[aux->vec]->nd[i-1]) + y;
     }                     
   }
  }
  
for(j=1;j<=n;j++)
   sol2+=sum[j][q];
  
sol+=2*sol2;
*/
//fprintf(fout,"%lld\n",sol);

//fclose(fin);
//fclose(fout);    
return 0;
}