小 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 < s_2 < \cdots < 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}$。