小红的孑串查询
题号：NC239873
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

孑鸽不要啊！！！哼哼哼啊啊啊啊啊啊啊啊1847/13/27/37/77*31*2啊啊啊啊啊啊
小红拿到了一个无限循坏小数。她想知道，在这个无限循坏小数的小数部分随机截取一个长度为k的孑串，该孓串含有多少个"114514"孑串？期望请对取模。

输入描述:

一个正整数seed
。

输出描述:

一个整数，代表孑串"114514"数量的期望。可以证明，该期望一定能写成的形式，分数取模的意义是，在区间找到一个整数x满足。
示例1

输入

复制 
4

输出

复制 
0

说明

不会真的有人以为长度4的孑串里包含114514吧？弱孑还是退散吧
示例2

输入

复制 
1919810

输出

复制 
500319971

说明

不会真的有人算不出长度1919810的孑串的期望吧？弱孑还是退散吧

备注:

哼哼妮可妮啊啊啊啊啊啊~~~~~~~~~~~~~~