题目内容

魔法工坊中，符文师需要制作总长为 $k$ 的符文卷轴。她可以重复使用三种基础符文，长度分别为 $a$、$b$、$c$，将符文按顺序首尾拼接，使得总长度恰好为 $k$。然而，由于符文能量冲突，长度为 $a$ 的符文后不得直接跟随长度为 $c$ 的符文，否则卷轴会失效。拼接的先后顺序不同则视为不同的方案。

为了在前端快速展示，工坊的魔法反应炉需要提前计算所有可能长度的方案数并缓存。你的任务是：对于给定的最大长度 $n$ 以及三种符文长度 $a, b, c$，计算出长度 $k = 1, 2, \dots, n$ 的合法拼接方案数，并对 $10^9+7$ 取模。

所有测试数据满足：测试用例数量 $T$ 不超过 $10$，$1 \le n, a, b, c \le 10^6$，且 $a, b, c$ 互不相等。单个测试文件中所有 $n$ 的总和不超过 $10^6$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试用例的数量。 接下来 $T$ 行，每行包含四个整数 $n, a, b, c$，依次代表最大卷轴长度和三种基本符文的长度，含义如上所述。

输出描述

对于每组测试数据，输出一行，包含 $n$ 个整数，第 $k$ 个整数表示长度为 $k$ 的合法拼接方案数模 $10^9+7$。整数之间用单个空格分隔。

样例1

输入

1
3 2 3 1

输出

1 2 3

说明

符文长度分别为 $a=2$，$b=3$，$c=1$，禁止长度为 $2$ 的符文后紧跟长度为 $1$ 的符文。

对于 $k=1$，只能使用一个 $c$，共 1 种方案。 对于 $k=2$，可以使用一个 $a$，或者两个 $c$（$c$ 后跟 $c$ 不违规），共 2 种方案。 对于 $k=3$，可以使用一个 $b$，或者 $c+a$（先 $c$ 后 $a$），或者三个 $c$；而 $a+c$ 被禁止，因此共 3 种方案。

最终输出 1 2 3。

样例2

输入

1
4 3 1 2

输出

1 2 4 7

说明

符文长度 $a=3$，$b=1$，$c=2$，禁止 $a$ 后紧跟 $c$。

手动枚举：

• $k=1$：仅能用 $b$，1 种。
• $k=2$：$b+b$ 或 $c$，2 种。
• $k=3$：$a$、$b+c$、$c+b$、$b+b+b$，共 4 种。
• $k=4$：所有组合总数为 7 种（$a+b$、$b+a$、$b+b+c$、$b+c+b$、$c+b+b$、$c+c$、$b+b+b+b$），且由于 $a+c$ 需要长度 $5$，无法出现在 $k=4$ 中，没有方案被排除。

因此输出 1 2 4 7。

样例3

输入

1
1 2 3 4

输出

0

说明

边界情况：三种符文长度分别为 $2,3,4$，均大于目标长度 $1$，无法拼接出总长为 $1$ 的卷轴，方案数为 0。