题目描述

“报告，我军已探出地雷阵中所有的地雷位置，并且还发现了一份使用说明书。”一个黑暗军团的小兵匆忙跑来，交给修罗王一张纸。

只见这张纸上面写道：“我是一颗萌萌的地雷，拆除我很容易，看到我身上标着的整数Ｎ了吗？你只要输入这个Ｎ位数中有多少个数中有偶数个数字4就可以把我拆除哦，加油！你行的。”

输入格式

一行一个整数 n

输出格式

输出这个Ｎ位数中有多少个数中有偶数个数字4

样例数据

input

2

output

73

数据规模与约定

1≤n≤18

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$