为了完成魔法仪式，还需要建造一个魔法祭坛。魔法祭坛是一个 的建筑，现在 zzj 和 liaoy 手上有无限多的 三种不同规格的魔法建筑材料。现在需要知道用这三种建筑材料一共有多少种建造出 的祭坛的方法。
输入包含一个整数 。
输出一个整数，表示一共有多少种方法。
答案可能过大，输出答案对 取模后的结果。
1
3
4
823
对于样例 1 ，一共有三种建造方案，分别是：ABC, AAB, ABB。
对于 也提供两种方案作为参考：
ABB AAB ACD CCD
其中不同字母代表不同建筑材料。