(mathcal{Descrtiption})
给定 ({a_n})，现进行 (m) 次操作，每次操作随机一个区间 ([l,r])，令其中元素全部变为区间最大值。对于每个 (i)，求所有可能操作方案最终得到的 (a_i) 之和。答案模 ((10^9+7))。
(n,qle400)。
(mathcal{Solution})
那什么我懒得写题解了就把草稿贴上来好了。（
[f(i,l,r,x):= ext{the operating ways that after }i ext{-th operation,}\
forall iin[l,r],a_ile x ext{ and }a_{l-1},a_{r+1}>x.\
f(i,l,r,x)=left(inom{l}{2}+inom{r-l+2}{2}+inom{n-r+1}{2}
ight)f(i-1,l,r,x)\
+sum_{p<l}(p-1)f(i-1,p,r,x)+sum_{r<p}(n-p)f(i-1,l,p,x).\
ext{Thus, the answer for }i ext{ can be represented as }r_i ext{, where}\
egin{aligned}
r_i&=sum_{x} xsum_{[l,r]
i i}f(q,l,r,x)-f(q,l,r,x-1)\
&=sum_{[l,r]
i i}sum_{x}-f(q,l,r,x)\
&=sum_{[l,r]
i i}g(q,l,r)~~~~(g(i,l,r):=sum_{x}-f(i,l,r,x)).
end{aligned}\
ext{Obviously, }g ext{'s expression is similar to }f ext{'s.}\
ext{Maintaining partial sum, this problem can be solved in }mathcal O(qn^2).
]
(mathcal{Code})
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
const int MAXN = 400, MOD = 1e9 + 7, IINF = 0x3f3f3f3f;
int n, m, a[MAXN + 5];
int g[2][MAXN + 5][MAXN + 5], sum[MAXN + 5];
inline int tot( const int u ) { return ( u * ( u + 1ll ) >> 1 ) % MOD; }
inline int mul( const int u, const int v ) { return 1ll * u * v % MOD; }
inline int sub( int u, const int v ) { return ( u -= v ) < 0 ? u + MOD : u; }
inline int add( int u, const int v ) { return ( u += v ) < MOD ? u : u - MOD; }
int main() {
scanf( "%d %d", &n, &m );
rep ( i, 1, n ) scanf( "%d", &a[i] );
a[0] = a[n + 1] = IINF;
rep ( l, 1, n ) {
int mxv = a[l];
rep ( r, l, n ) {
mxv = mxv < a[r] ? a[r] : mxv;
int mnv = a[l - 1] < a[r + 1] ? a[l - 1] : a[r + 1];
if ( mnv > mxv ) g[0][l][r] = sub( mxv, mnv < IINF ? mnv : 0 );
}
}
for ( int sta = 1, i = 1; i <= m; sta ^= 1, ++i ) {
memset( sum, 0, sizeof sum );
rep ( l, 1, n ) rep ( r, l, n ) {
g[sta][l][r] = add( sum[r], mul( add( add( tot( l - 1 ),
tot( r - l + 1 ) ), tot( n - r ) ), g[!sta][l][r] ) );
sum[r] = add( sum[r], mul( l - 1, g[!sta][l][r] ) );
}
memset( sum, 0, sizeof sum );
per ( r, n, 1 ) per ( l, r, 1 ) {
g[sta][l][r] = add( g[sta][l][r], sum[l] );
sum[l] = add( sum[l], mul( n - r, g[!sta][l][r] ) );
}
}
rep ( i, 1, n ) {
int ans = 0;
rep ( l, 1, i ) rep ( r, i, n ) ans = add( ans, g[m & 1][l][r] );
printf( "%d%c", ans, i < n ? ' ' : '
' );
}
return 0;
}