题目描述

一个数字串，包含 $n$个数字，呈规律性的变化： 第一个数字是 $1$，第二个数字是 $2$， 第 $i$个数字是（第（$i-1$）位数字）$\%3$+（第（$i-2$）位数字）$+1$。

比如：第三个数字为（$2$）$\%3$+（$1$）$+1=5$；第四个数字为（$5$）$\%3$+（$2$）$+1=5$；以此类推……（是否正确？）

请你编写程序求出这个数字串中可以被 $7$整除的数字个数。

输入格式

只有一个整数 $n$。

输出格式

只有一个输出，表示这 $n$个数字中可以被 $7$整除的数字个数。

777

110

3

0

4

0

数据规模与约定

对于 $100\%$的数据，$3 \le n \le 10^6$。

（$3 \le n \le 1000000$）