该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个正整数 $M$，要求找到一个正整数 $N$ 和一个非负整数序列 $A = (A_1, A_2, \dots, A_N)$，使得满足以下条件：

• $1 \le N \le 20$
• $0 \le A_i \le 10$，对于 $1 \le i \le N$
• $\sum_{i=1}^{N} 3^{A_i} = M$

可以证明，总是存在一组满足条件的 $N$ 和序列 $A$。

输入格式

一个整数 $M$ ($1 \le M \le 10^5$)。

输出格式

首先输出一个整数 $N$，表示序列 $A$ 的长度。

接着输出 $N$ 个整数，表示序列 $A$。

如果存在多组满足条件的解，输出任意一组即可。

样例

6

2
1 1

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

解释

在此样例中，$N=2$，$A=(1, 1)$，我们有 $\sum_{i=1}^N 3^{A_i} = 3 + 3 = 6$，符合题意。