Description

奶奶家要养很多的鸡，每天要卖也要买很多的鸡，但是奶奶每天的钱不是固定的，今天需要根据奶奶的钱来买鸡。 鸡场里有4种鸡可以购买，分别是公鸡5元一只，母鸡3元一只，小鸡2只一元，雏鸡3只一元。奶奶现在手里有n元钱必须要恰好买n只鸡，现在要你帮忙看看奶奶有多少种方案可以去买。

Format

Input

第一行为整数 n（10≤n≤800）

Output

输出若有解，前 cnt 行每行输出一种合法组合公鸡、母鸡、小鸡、雏鸡，中间用空格隔开。 第 cnt+1 行输出方案总数 cnt。 若 cnt = 0，仅输出一行 0。

Samples

10  

0 2 8 0
1