题目描述

请编程求出所有 n 位数中有多少个数中有偶数个数字3。

输入格式

一行，一个正整数 n。

输出格式

仅一个正整数，表示有多少个数有偶数个 3 的。（结果对12345求余）

样例

输入

2

输出

73

提示

数据范围：0 < n < 1000.