说明

小A觉得无聊，于是开始悠闲的数数（四声）。

因为小A非常喜欢数字7，于是他想数一数，在所有的N位数中，有多少个数字中有数字7，且拥有数字7的数量为偶数，当N很大的时候，结果很大，需要输出结果对12345取余的值。

输入格式

一行，一个数字N，不超过1000。

输出格式

一行，输出满足条件的数的个数对12345取余的结果。

样例

2

73

提示

样例说明
在 10 - 99 中
有 0 个 7 的数有 72 个
有 2 个 7 的数有 1 个