题目描述

定义 $f(s,a,b,c)=\sum\limits_{i+j+k=s}\begin{pmatrix}a\\i\end{pmatrix}\begin{bmatrix}b\\j\end{bmatrix}\begin{Bmatrix}c\\k\end{Bmatrix}$。

给定正整数 $n$ 和 $m$ 对三元组 $(a_i,b_i,c_i)$，其中 $0\le a_i,b_i,c_i\le n$。定义 $g(k)=\sum\limits_{i=1}^mf(k,a_i,b_i,c_i)$。

分别求出 $g(0),g(1)\dots g(n)$，并对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，第 $i$ 行三个整数 $a_i,b_i,c_i$。

输出格式

一行 $n+1$ 个整数，表示答案。

样例输入一

5 6
5 1 3
2 5 4
3 2 3
1 0 0
4 1 3
4 5 1

样例输出一

1 1 51 434 1432 2498

数据范围

对于所有数据，满足 $1\le n\le 2000,1\le m\le 10000,0\le a_i,b_i,c_i\le n$。

大样例