Dulceață 是一种通常在早餐时抹在面包上食用的甜水果酱。Dulceață 可以用很多种水果制作，但一种传统的选择是 vișine（酸樱桃）。制作酸樱桃 Dulceață，首先需要将樱桃与糖混合并静置一晚。到第二天早上，酸樱桃就会浸泡在它们的糖浆汁中。加入一点柠檬汁，然后用小火慢炖，直到混合物呈现深红色并达到完美的浓稠度。

有无限多种类型的酸樱桃，用正整数 $1, 2, 3, \dots$ 编号。每种类型 $i$ 都有一个关联的甜度值，形式为 $2^i - 1$。你想制作有史以来最棒的 Dulceață，其甜度为 $n$。你将购买 $k$ 个樱桃来制作 Dulceață，但你不知道 $k$ 的最佳值。因此，你决定对于介于 $1$ 和 $p$ 之间（含）的每个整数 $k$，计算有多少种制作 Dulceață 的方法。由于这些数字可能非常大，请将它们对 $10^9 + 7$ 取模后输出。

如果存在某种类型 $i$，使得两种制作方法中使用的类型 $i$ 的樱桃数量不同，则认为这两种制作 Dulceață 的方法是不同的。

输入格式

输入的第一行也是唯一一行包含两个整数 $n$ 和 $p$（$1 \le n \le 10^{18}$，$1 \le p \le 1000$）。

输出格式

输出 $p$ 个整数，其中第 $k$ 个整数表示用 $k$ 个酸樱桃制作甜度为 $n$ 的 Dulceață 的方法数模 $10^9 + 7$ 的余数。

样例

输入样例 1

4 2

输出样例 1

0 1

输入样例 2

14 4

输出样例 2

0 1 0 1

输入样例 3

9 3

输出样例 3

0 0 2