数列
题号：NC219127
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

数列f(n)=f(n-1)+f(n-2)+f(n-3)
假定式子从0开始，且f(0)=1，f(1)=2，f(2)=3。
求出f(n)的大小。（f(n)可能很大，输出f(n)对88888888取模的结果）

输入描述:

输入一个n，表示第n项。1<=n<=2*10^9

输出描述:

一个T。表示答案
示例1

输入

复制 
10

输出

复制 
423
示例2

输入

复制 
100

输出

复制 
24007827