问题描述

在所有的N位数中，有多少个数中有偶数个数字3？

输入数据

从problem1.in中读入一个数N。1<=N<=1000。

输出数据

将答案输出到problem1.out中。 由于结果可能很大，你只需要输出这个答案对12345取模的值

样例输入：

2

样例输出：

73