描述

题目: 在帕斯卡三角形中能够发现一些性质，如通过将帕斯卡三角形对角线上的数字相加，便可以找到斐波那契数列1, 1, 2, 3, 5, 8, 13, 21, 34, …，如下图所示：

在上图中，帕斯卡三角形的每一行的首尾位置都是1。在三角形中间位置上的每个数字都是其上方紧邻的两个数字之和 。第0行只有一个数字1。第N 行有 N+1 个数字。

输入输出格式

输入

一个整数，表示斐波那契数列中的一个元素： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 .... 我们保证这个整数不会超过 1,000,000。

输出

根据输入的数据，输出帕斯卡三角形中某条对角线上的所有数字，这些数字相加之和等于给定整数，按照从三角形左下方到右上方出现的顺序依次输出，中间由一个空格隔开。

8

1 4 3

832040

1 28 351 2600 12650 42504 100947 170544 203490 167960 92378 31824 6188 560 15

限制

• 时间限制：1 秒
• 空间限制：64 MB
• 输入的每个斐波那契数 F 满足 1 ≤ F ≤ 1,000,000
• 保证输入的 F 一定是斐波那契序列中某一项（F₀=1, F₁=1, F₂=2, F₃=3, F₄=5, F₅=8, F₆=13, ...）
• 最大可能的 k 不超过 30（因为 F₃₀ = 832040，F₃₁ = 1346269 > 1e6），故所有二项式系数均可使用 32 位整数安全计算