C. 非空子集

Cyhlnj天天切大火题。

有一天他突然觉得切火题没什么意思，于是就翻开了这样的一道题目：

• 给你三个数，要你求从中选出一个非空子集使这个子集中所有数的最大公因数(greatest common divisor,GCD)恰好为，最小公倍数(least common multiple,LCM)恰好为的方案数。

Cyhlnj觉得这个题太傻逼了，于是他对此进行了一些加强：他会给出次询问，每次询问选出的子集必须包含某个正整数的前提下，方案数会是多少。

因为答案可能很大，所以你需要输出答案对取模后的结果。

数据第一行包含四个正整数，意义见题目描述。

接下来行每行一个正整数，表示询问选出的子集必须包含某个正整数的前提下，方案数会是多少。

输出包括行，其中第一行一个数表示不加任何限制的情况下满足条件的方案数对取模后的结果，接下来行每行一个数表示选出的子集中包含某个正整数且满足条件的方案数对取模后的结果。

见附加文件

对于的数据，。