题目描述

在所有十进制 $n$ 位正整数中，有多少个数含有偶数个数字3？0个也属于偶数个。首位不能是0。请输出答案对12345取余的结果。

输入格式

输入一个整数 $n$。

输出格式

输出答案对12345取余的结果。

样例

2

73

数据范围

$1\le n\le1000$。