该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

又一轮生化武器的拍卖结束了，保护伞公司的经费紧张终于得到了缓解，因此公司终于有钱买量筒了。
公司买了$n$个量筒，第$i$个量筒的容积为$i!$毫升（也就是$1 \times 2 \times ... \times i$）。
当需要量取$a$毫升的试剂时，设第$i$种量筒使用$a_i(a_i>=0)$次，那么我们选取的测量方案将使得：
1.$1!a_1+2!a_2+...+n!a_n=a$（即恰好量出$a$毫升）。
2.$a_1+a_2+...+a_n$最小（即总使用次数最小）。
未来$q$天内保护伞公司仍将继续T病毒的研究，第$i$天需要$l_i \sim r_i($即$l_i,l_i+1,l_i+2,...,r_i)$毫升的试剂各一次，我们希望知道每天每种量筒使用了多少次。

Format

Input

每个测试点仅包含一组输入数据。
第一行两个整数$n,q(2<=n<=9,1<=q<=200000)$。
接下来$q$行，每行两个整数$l_i,r_i(1<=l_i<=r_i<=10^{18})$。

Output

按照输入顺序，对于每天输出一行$n$个用空格隔开的整数，第$i$个数表示第$i$种量筒这一天内使用了几次，由于使用次数可能过多，你只需要输出其除以$1000000007$所得余数。
行末不要输出多余空格。

Sample 1

Input

5 2
1 6
24 24

Output

3 6 1 0 0
0 0 0 1 0

Limitation

2s, 1GB for each test case.

Source

Vijos Original