#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=,MOD=;

int n,first[maxn],tot=,top[maxn],deep[maxn],pos[maxn],q,ansz[maxn],size[maxn],f[maxn],dfsnum=;

long long anss[maxn*];

struct edge{int from,v;}e[maxn*];

struct node{int l,r,delta,sum;}t[maxn*];

struct numbers{int num,ord;bool flag;}num[maxn*];

void insert(int u,int v)

{tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

bool cmp(numbers a,numbers b)

{return a.num<b.num;}

void dfs1(int x,int fa)

{

    size[x]=;

    for(int i=first[x];i;i=e[i].from)

     if(e[i].v!=fa)

      {

          int y=e[i].v;

          f[y]=x;

          deep[y]=deep[x]+;

          dfs1(y,x);

          size[x]+=size[y];

      }

}

void dfs2(int x,int tp,int fa)

{

    pos[x]=++dfsnum;

    top[x]=tp;

    int k=;

    for(int i=first[x];i;i=e[i].from)

     if(e[i].v!=fa&&size[e[i].v]>size[k])k=e[i].v;

    if(k==)return;

    dfs2(k,tp,x);

    for(int i=first[x];i;i=e[i].from)

     if(e[i].v!=fa&&e[i].v!=k)dfs2(e[i].v,e[i].v,x);

}

void build(int k,int l,int r)

{

    t[k].l=l;t[k].r=r;t[k].delta=;t[k].sum=;

    if(l==r)return;

    int mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    t[k].sum=t[k<<].sum+t[k<<|].sum;

}

void add(int k,int l,int r)

{

    int left=t[k].l,right=t[k].r;

    if(l<=left&&right<=r)

     {

         t[k].delta++;

         t[k].sum+=right-left+;

         return;

     }

    if(t[k].delta)

     {

         t[k<<].delta+=t[k].delta;

         t[k<<].sum+=(t[k<<].r-t[k<<].l+)*t[k].delta;

         t[k<<|].delta+=t[k].delta;

         t[k<<|].sum+=(t[k<<|].r-t[k<<|].l+)*t[k].delta;

         t[k].delta=;

     }

    int mid=(left+right)>>;

    if(l<=mid)add(k<<,l,r);

    if(r>mid)add(k<<|,l,r);

    t[k].sum=t[k<<].sum+t[k<<|].sum;

}

long long query(int k,int l,int r)

{

    int left=t[k].l,right=t[k].r;

    if(l<=left&&right<=r)return t[k].sum;

    if(t[k].delta)

     {

         t[k<<].delta+=t[k].delta;

         t[k<<].sum+=(t[k<<].r-t[k<<].l+)*t[k].delta;

         t[k<<|].delta+=t[k].delta;

         t[k<<|].sum+=(t[k<<|].r-t[k<<|].l+)*t[k].delta;

         t[k].delta=;

     }

    int mid=(left+right)>>;

    long long ans=;

    if(l<=mid)ans=query(k<<,l,r);

    if(r>mid)ans+=query(k<<|,l,r);

    return ans;

}

void solve_ins(int x,int y)

{

    while(top[x]!=top[y])

     {

         if(deep[top[x]]<deep[top[y]])swap(x,y);

         add(,pos[top[x]],pos[x]);

         x=f[top[x]];

     }

    if(pos[x]>pos[y])swap(x,y);

    add(,pos[x],pos[y]);

}

long long solve_sum(int x,int y)

{

    long long ans=;

    while(top[x]!=top[y])

     {

         if(deep[top[x]]<deep[top[y]])swap(x,y);

         ans+=query(,pos[top[x]],pos[x]);

         x=f[top[x]];

     }

    if(pos[x]>pos[y])swap(x,y);

    ans+=query(,pos[x],pos[y]);

    return ans;

}

int main()

{

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

    int u;

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

     {

         scanf("%d",&u);

         insert(u+,i);

         insert(i,u+);

     }

    int ll,rr,zz;

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

     {

         scanf("%d%d%d",&ll,&rr,&zz);ll++;rr++;zz++;

         ansz[i]=zz;

         num[i*-].num=ll-;num[i*-].ord=i;num[i*-].flag=;

         num[i*].num=rr;num[i*].ord=i;num[i*].flag=;

     }

    sort(num+,num+q*+,cmp);

    build(,,n);dfs1(,-);dfs2(,,-);

    int now=;

    memset(anss,,sizeof(anss));

    for(int i=;i<=q*;i++)

     {

         if(num[i].num>now)

          for(int j=now+;j<=num[i].num;j++)solve_ins(,j);

         now=num[i].num;

         if(num[i].flag)anss[num[i].ord]+=solve_sum(,ansz[num[i].ord]);

          else anss[num[i].ord]-=solve_sum(,ansz[num[i].ord]);

     }

    for(int i=;i<=q;i++)printf("%lld\n",anss[i]%MOD);

    return ;

}