题目描述

据说，每个人都有自己的幸运数字，小D也不例外。小D认为，如果某个非负整数恰好包含偶数个1（包括 0 个），那么这个数字就是他的幸运数字。现在，小D想知道，在长度为N 的非负整数中，一共有多少个属于他的幸运数字。你能帮他计算一下吗？

注意：本题中长度为N的非负整数，指长度为N但不包含前导 0 的非负整数，例如长度为 2 的非负整数共有 90 个，数值范围 10∼99。

输入格式

一个正整数N

2≤n≤18

输出格式

符合条件的N位数个数

输入样例 #1

2

输出样例 #1

73

输入样例 #2

3

输出样例 #2

674

输入样例 #3

4

输出样例 #3

6292

数据范围

2≤n≤18