You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

对于一个正整数，如果它可以拆分成若干个不同的正整数的阶乘之和（阶乘定义：(k! = $1 \times 2 \times \cdots \times k$)，其中 k 为正整数），则称这种拆分为“阶乘拆分”。

例如，9 = 1! + 2! + 3! = 1 + 2 + 6 是一个阶乘拆分，而 5 无法拆分成不同的阶乘数之和。

给定正整数 n，请你判断是否存在这样的拆分。若存在，请输出从大到小的拆分方案。可以证明，若存在，方案唯一。

输入格式

输入一行一个整数 n 。

输出格式

若存在，按从大到小顺序输出拆分中的每一个阶乘数，相邻两个数之间用一个空格隔开。 若不存在，输出 -1。

9

6 2 1

4

-1

2

2

43914361

39916800 3628800 362880 5040 720 120 1

提示

样例解释

• 样例 1：9 = 6 + 2 + 1 = 3! + 2! + 1!。
• 样例 2：4 无法表示为不同阶乘数的和。
• 样例 3：2本身就是 2!，是一个合法的拆分。
• 样例 3：43914361 = 11! + 10! + 9! + 7! + 6! + 5! + 1! =39916800 +3628800+362880+5040+720+120+1

数据范围

对于 $100\%$ 的数据，$1 \le n \le 1000$。