小 Z 刚刚学习了二进制！二进制数是用 $$$0$$$ 和 $$$1$$$ 两个数码来表示的数。它的基数为 $$$2$$$，进位规则是"逢二进一"，借位规则是"借一当二"。对于一个长度为 $$$m$$$ 的二进制串，其可以表示 $$$[0\sim 2^m)$$$ 的值。聪慧的小 Z 很快引申到了 $$$n$$$ 进制数，她意识到，对于任意大于 $$$1$$$ 的正整数 $$$n$$$，一个长度为 $$$m$$$ 的 $$$n$$$ 进制数可以表示所有 $$$[0\sim n^m)$$$ 的值。但小 Z 并不满足于正整数，她还想知道某种特殊定义下的 $$$a/b$$$ 进制下的情况......

小 Z 的问题形式化地表示如下，给出一个正数 $$$n$$$ （其中 $$$n$$$ 以 $$$x = n \times b^m$$$ 的形式给出，$$$x$$$ 是一个不超过 $$$10^{18}$$$ 的正整数）、正整数 $$$m,a,b$$$ 和一个长度为 $$$m+1$$$ 的序列 $$$c_i$$$（下标从 $$$0$$$ 开始），问是否能选出一个长度为 $$$k$$$ 的非空整数序列 $$$s$$$，满足 $$$0\le s_1 \lt s_2 \lt \cdots \lt s_k \le m$$$，使得 $$$n = \sum_{i=1}^k c_{s_i} \times (\frac{a}{b})^{s_i}$$$。在有解的情况下，小 Z 还希望这个序列的长度 $$$k$$$ 尽量小，并想知道在满足 $$$k$$$ 最小情况下的方案数，以及其中任意一种方案。若无解的话，只要告诉小 Z 一行一个 $$$-1$$$ 表示无解即可。

小 Z 觉得 $$$a=b$$$ 非常的简单，所以她保证了 $$$a \ne b$$$；但是她又觉得这道题非常的困难，所以她又保证了对于任意 $$$c_i$$$，$$$c_i$$$ 与 $$$a$$$、$$$b$$$ 同时互质。小 Z 认为大部分选手会使用 C++ 作答，所以她还贴心的保证了对于任意 $$$i (0\le i\le m)，c_i \times a_i^i \cdot b_i^{m-i} \le 10^{18}$$$。