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