Migrated from Lutece 1587 失恋772002天

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

日天失恋了，为了安慰他，锅爷决定带他去抓娃娃。锅爷买了$111$个币，连抓$108$把却一无所获。锅爷说：“这个娃娃机很邪”，于是把剩下$3$个币给了日天。日天仅用$3$把，就抓获一只海绵宝宝、一只卡布达和一只美羊羊。于是，他决定每天晚上和一只娃娃睡觉，来获取心灵上的慰藉。但是，日天是个有原则的人，他决不允许自己连续三天和三个不同的人睡觉，娃娃也是如此。请你来计算，按照日天的要求，他失恋的前$N$天，共有多少种不同的睡觉方式呢？

Input

一个整数$N(1\leq N\leq 772002)$，代表日天的失恋天数。

Output

输出日天失恋前$N$天的睡觉方案数对$UESTC-ACM-2017$新人交流群群号:$554056561$取模的结果。

Samples

1

3

2

9

3

21

Note

样例$3$，以$H$代表海绵宝宝、$K$代表卡布达、$M$代表美羊羊，日天这$3$天共有如下$21$种不同的睡觉方式： $HHH、HHK、HHM、HKH、HKK、HMH、HMM、$ $KHH、KHK、KKH、KKK、KKM、KMK、KMM、$ $MHH、MHM、MKK、MKM、MMH、MMK、MMM$

Resources

每周一题 Div2