题目描述

猪猪 Hanke 有一只烤鸡，并且准备使用 $10$ 种配料进行调味。

每种配料可以放 $1$ 到 $3$ 克。

一只烤鸡的美味程度定义为这 $10$ 种配料质量之和。

现在给定一个整数 $n$，表示目标美味程度。

请输出所有满足以下条件的配料搭配方案：

• 一共有 $10$ 种配料；
• 每种配料的质量只能是 $1$、$2$ 或 $3$ 克；
• $10$ 种配料的质量之和恰好等于 $n$。

输入格式

输入一个正整数 $n$，表示目标美味程度。

输出格式

第一行输出满足条件的方案总数。

接下来按照字典序输出所有方案，每个方案占一行。

每行输出 $10$ 个整数，依次表示 $10$ 种配料所放的质量，相邻整数之间用一个空格分隔。

如果不存在符合要求的方案，则只输出一行：

0

样例

11

10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

数据范围

$n \le 10000$。

来源：洛谷P2089