题目描述

       朱老师对现在一个月0.3w的工资很不满意，于是准备外出兼职去搬砖。朱老师到达工厂，包工头对朱老师说：你面前有两块类型的板砖A和B，假设这些砖有无限块。我需要你搬n块（不能多也不能少）搬砖到指定地点。但是如果想要搬B类型的砖，就必须要搬两块。

       麻烦你帮小朱老师算一下，小朱老师有多少种办法可以将n块板砖搬到指定地点。并且按字典序从小到大输出所有可能性

输入

第一行包含一个正整数n，表示有n块板砖。

输出

有多少种办法可以将n块板砖搬到指定地点和所有可能性。

Samples

2

2
AA
BB

数据范围

对于100％的数据１＜＝ｎ＜＝20