所有人，都有一段支离破碎的过去。
你有 $n$ 段过去的经历，有时顺利，有时不顺，于是你用一个评价值 $a_i$ 来描述你的第 $i$ 段经历，它们构成了长度为 $n$ 的序列 $a$。你决定对过去进行反思总结，反思深度为 $d$。如果 $d\geq1$，那你就要算出 $a$ 的所有子区间的和之和；如果 $d\geq2$，那你还要算出 $a$ 的所有子区间的极差之和；如果 $d\geq3$，那你也要算出 $a$ 的所有子区间的平均值之和。
定义：子区间是指序列中连续的一段；区间和为区间所有数相加的和；区间极差为区间的最大值减去最小值；区间的平均值为区间和除以区间元素个数。
为了输出方便，输出平均值时请乘上 $n!$，所有输出对 $1336363663$ 取模。

第一行，两个整数 $n,d$，表示经历的段数、反思的深度。
第二行，$n$ 个整数 $a_i$，表示第 $i$ 段经历的评价值。
$1\le n\le3\times{10}^6,0\le d\le3,1\le a_i\le{10}^9$

$d$ 行每行一个整数。第一个（如果有）表示子区间和的和，第二个（如果有）表示子区间极差的和，第三个（如果有）表示子区间平均值的和乘以 $n!$。上述均对 $1336363663$ 取模。