/**************************************************************
    Problem: 4515
    User: wxx_louisa
    Language: C++
    Result: Accepted
    Time:13936 ms
    Memory:36612 kb
****************************************************************/

#include<cstdio>
#include<algorithm>
#define ll long long
#define N 200005
#define M 400005
#define inf 123456789123456789ll
using namespace std;
int n,m;
ll ans;
,vet[N],head[N],son[N],size[N],top[N],id[N],tid[N],f[][],next[N],pri[N],dep[N];
ll dis[N],A[M],B[M],val[M],tag[M];
void add(int u,int v,int w)
{
    edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
    pri[edgenum]=w;
}
ll min(ll a,ll b)
{
    if(a<b)return a;else return b;
}
void build(int p,int st,int ed)
{
   val[p]=inf;;
   if(st<ed)
   {
      build(p+p,st,mid);build(p+p+,mid+,ed);
   }
}
void dfs1(int u,int ff,int deep)
{
    ;dep[u]=deep;
    )
    {
       int v=vet[e];
       if(v!=ff){
          dis[v]=dis[u]+pri[e];f[v][]=u;
          dfs1(v,u,deep+);
          if(size[v]>size[son[u]])son[u]=v;
          size[u]+=size[v];
       }
       e=next[e];
    }
}
void dfs2(int u,int ff,int anc)
{
    top[u]=anc;
   ;i<=;i++)
    {
        <<i)>dep[u])break;
        f[u][i]=f[f[u][i-]][i-];
    }
   int e=head[u];tot++;tid[u]=tot;id[tot]=u;
   )return;
   dfs2(son[u],u,anc);
   )
   {
       int v=vet[e];
       if(v!=ff&&v!=son[u]){
          dfs2(v,u,v);
       }
       e=next[e];
   }
}
void maintain(int p,int st,int ed)
{

    ]);else val[p]=inf;
    if(tag[p])val[p]=min(val[p],min(dis[id[st]]*A[p],dis[id[ed]]*A[p])+B[p]);
    //printf("main==%d %d %d %lld\n",p,st,ed,val[p]);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    ;k>=;k--)
    {
       <<k)>=dep[y]){
          x=f[x][k];
       }
       if(dep[x]==dep[y])break;
    }
    ;k>=;k--)
    {
      if(f[x][k]!=f[y][k]){
        x=f[x][k];y=f[y][k];
      }
    }
    ];
    return x;
}
void update(int p,int l,int r,ll a,ll b)
{
   //printf("up===%d %d %d %lld %lld\n",p,l,r,a,b);
    ){tag[p]=;A[p]=a;B[p]=b;}else
    {
        ll x1=dis[id[l]]*a+b,y1=dis[id[r]]*a+b,x2=dis[id[l]]*A[p]+B[p],y2=dis[id[r]]*A[p]+B[p];
        ;
        if(x1<=x2&&y1<=y2){
           A[p]=a,B[p]=b;
        }else if(x1>=x2&&y1>=y2)return;else if(a<A[p])
        {
            ll tmp=(b-B[p])/(A[p]-a)+;
            if(tmp<=dis[id[mid]]){
                swap(a,A[p]);swap(b,B[p]);update(p+p,l,mid,a,b);
            },mid+,r,a,b);
        }else{
            ll tmp=(B[p]-b-)/(a-A[p]);
            if(tmp>dis[id[mid]])
            {
                swap(a,A[p]);swap(b,B[p]);
                update(p+p+,mid+,r,a,b);
            }else update(p+p,l,mid,a,b);
        }
    }
    maintain(p,l,r);//important!
}
void ins(int p,int l,int r,int st,int ed,ll a,ll b)
{
    //printf("==%d %d %d %d %d %lld %lld\n",p,l,r,st,ed,a,b);
    if(l==st&&r==ed){
        update(p,l,r,a,b);return;
    };
    ,l,r,mid+,ed,a,b);
     ,mid+,r,mid+,ed,a,b);
    maintain(p,st,ed);
}
void query(int p,int l,int r,int st,int ed)
{
   // printf("query===%d %d %d\n",p,l,r);
    if(l==st&&r==ed){ans=min(ans,val[p]);return;}
    if(tag[p])ans=min(ans,min(dis[id[l]]*A[p]+B[p],dis[id[r]]*A[p]+B[p]));
    ;
    if(r<=mid)query(p+p,l,r,st,mid);else
     ,l,r,mid+,ed);else
       query(p+p,l,mid,st,mid),query(p+p+,mid+,r,mid+,ed);
}
ll que(int x,int y)
{
    ans=inf;
    while(top[x]!=top[y]){
       if(dep[top[x]]<dep[top[y]])swap(x,y);
       query(,tid[top[x]],tid[x],,n);
       x=f[top[x]][];
    }
    ,tid[y],tid[x],,n);
    return ans;
}
void work(int x,int y,ll a,ll b)
{
    //printf("work==%d %d \n",x,y);
    while(top[x]!=top[y])
    {
      ,tid[top[x]],tid[x],,n,a,b);
      x=f[top[x]][];
    }
    ,tid[y],tid[x],,n,a,b);
}
int main()
{
    scanf("%d%d",&n,&m);
    ;i<=n-;i++)
    {
       int u,v,w;
       scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);
    }
    dfs1(,,);dfs2(,,);
    //for(int i=1;i<=n;i++)printf("===%d %d %d\n",son[i],tid[i],top[i]);
    build(,,n);
    while(m--)
    {
        int op;scanf("%d",&op);
        )
        {
            int x,y;ll a,b;
            scanf("%d%d%lld%lld",&x,&y,&a,&b);
            int ff=lca(x,y);
            ll tmp=dis[x]*a+b;work(x,ff,-a,tmp);
            tmp=a*(dis[x]-dis[ff]*)+b;work(ff,y,a,tmp);
        }else{
            int x,y;
            scanf("%d%d",&x,&y);int ff=lca(x,y);
            printf("%lld\n",que(x,y));
        }
    }
    //for(int i=1;i<=15;i++)printf("%lld ",val[i]);
 } 

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 1000000007
#define ll long long
#define N 1000100
using namespace std;
ll jie[N],g[N],f[N],ni[N];
ll quickmi(ll x)
{
    ll tmp=,k=mo-,a=x;
    )
    {
        ==)
        {
            tmp=tmp*a%mo;
        }
        a=a*a%mo;
        k/=;
    }
    return tmp;
}
ll cc(int n,int m)
{
    return jie[n]*ni[m]%mo*ni[n-m]%mo;
}
int main()
{
    jie[]=;
    ;i<=;i++)jie[i]=(jie[i-]*i)%mo;
    ni[]=;ni[]=;
    ;i<=;i++)
      {
          ni[i]=quickmi(jie[i]);
      }
    f[]=;f[]=;f[]=;f[]=;
    g[]=;g[]=;g[]=;g[]=;
    ;i<=;i++)
    {
            f[i]=g[i-]%mo;
            g[i]=(f[i-]+g[i-])%mo*i%mo;
    }
    int cas,n,m;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        ll ans=cc(n,m)*f[n-m]%mo;
        printf("%lld\n",ans);
    }
 } 

#include<cstdio>
#include<cmath>
#define inf 1000000000
#include<algorithm>
#define N 3010
#define ll long long
using namespace std;
ll n,m;
ll q[N],s[N],f[N],a[N],dp[N];
bool pd1(int x,int k,int j)
{
  //printf("%d %d %d\n",x,k,j);
  ll fenzi=f[j]-f[k]+s[j]*s[j]-s[k]*s[k];
  ll fenmu=(s[j]-s[k])*2ll;
  //printf("===%d %d %d %d %d\n",x,fenzi,fenmu,k,j);
  return x*fenmu>=fenzi;
}
int sqr(int x)
{
    return x*x;
 }
bool pd2(int k,int j,int i)
{
  ll fenzi1=f[j]-f[k]+s[j]*s[j]-s[k]*s[k];
  ll fenmu1=2ll*(s[j]-s[k]);
  ll fenzi2=f[i]-f[j]+s[i]*s[i]-s[j]*s[j];
  ll fenmu2=2ll*(s[i]-s[j]);
  //printf("===%d %d %d %d\n",k,j,i,fenzi
  return fenzi2*fenmu1<fenmu2*fenzi1;
}
int main()
{
    scanf(]=;
    ;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        s[i]=s[i-]+a[i];
    }
    ;i<=n;i++)f[i]=inf;f[]=;
    ;j<=m;j++)
    {
        ,tail=;q[]=j-;
        for(int i=j;i<=n;i++)
        {
            ]))head++;
            int u=q[head];
            //printf("%d %d %d\n",i,j,u);
            dp[i]=f[u]+sqr(s[i]-s[u]);
            //printf("%d %d %d %d\n",i,j,u,dp[i]);
            ],q[tail],i))tail--;
            ++tail;q[tail]=i;
        }
        ;i<=n;i++)f[i]=dp[i],dp[i]=inf;
    }
    //printf("%d\n",s[n]);
    printf("%lld",m*f[n]-s[n]*s[n]);
}