题目描述

奥数课上，马克遇到一个数字问题，想请会编程的你用程序解决一下。一个n位数，它由数字4,5,6组成，且它的任意连续两位数都不等于45,54,55或63，请你计算并输出满足条件的自然数的个数。如果继续要求数字4,5,6每个数字都至少要出现一次，满足条件的自然数又有多少个？

输入格式

一个整数n(n<=20)

输出格式

两个用空格分隔的整数。

样例

9

177 79

来源：六年奥数归纳与递推