3 的幂

题目描述

给你一个正整数 $M$。

请找出满足以下所有条件的正整数 $N$ 和非负整数序列 $A = (A_1, A_2, \ldots, A_N)$：

• $1 \le N \le 20$
• $0 \le A_i \le 10$ $(1 \le i \le N)$
• $\displaystyle \sum_{i=1}^N 3^{A_i} = M$

可以证明，在约束条件下，总存在至少一对满足条件的 $N$ 和 $A$。

输入格式

输入按以下格式从标准输入给出：

$M$

输出格式

按以下格式输出满足条件的 $N$ 和 $A$：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

如果存在多组合法的 $N$ 和 $A$，输出任意一组均可。

样例

6

2
1 1

例如，当 $N=2$、$A=(1,1)$ 时，有 $\displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6$，满足所有条件。

另一个例子是 $N=4$、$A=(0,0,1,0)$，也满足条件。

100

4
2 0 2 4

59048

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

注意条件 $1 \le N \le 20$。

数据范围

• $1 \le M \le 10^5$

提示

答案不唯一,输出任意合法解即可。