# ZeroJudge - f738: 老鼠的數列
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f738
###### tags: `ZeroJudge` `輸出入最佳化` `編譯器最佳化`

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <iostream>
using namespace std;
#define MOD 1000000007

char ReadChar() {
	static int counts = 1 << 16;
	static const int length = 1 << 15;
	static char buffer[length];
	static char *pointer = buffer, *end = buffer;
	if (pointer == end) {
		if (counts < length)
			return EOF;
		counts = fread(buffer, 1, length, stdin);
		end = buffer + counts;
		pointer = buffer;
	}
	return *(pointer++);
}

template <class type>
bool ReadNumber(type *number) {
	static char buffer;
	while ((buffer = ReadChar()) < '-')
		if (buffer == EOF)
			return false;
	*number = buffer - '0';
	while ((buffer = ReadChar()) >= '0')
		*number = (*number << 3) + (*number << 1) + buffer - '0';
	return true;
}

class Printer {
public:
	static const int length = 1 << 16;
	char buffer[length], *pointer, *end;

	Printer():pointer(buffer), end(pointer + length - 1) {}

	~Printer() {
		*pointer = '\0', printf("%s", buffer);
	}

	void PrintNumber(int number) {
		static char digits[12];
		int index = 0;
		digits[index] = '\n'; ++index;
		if (!number) {
			*(digits + index) = '0';
			++index;
		}
		while (number) {
			*(digits + index) = (number % 10) + '0';
			++index;
			number /= 10;
		}
		while (index) {
			if (pointer == end) {
				*pointer = '\0';
				printf("%s", buffer);
				pointer = buffer;
			}
			--index; *pointer = *(digits + index); ++pointer;
		}
	}

} *printer = new Printer();

int lucas[1000001] = { 2, 1, 3 };

void Initialize() {
	for (int i = 3; i <= 1000000; ++i) 
		lucas[i] = (lucas[i - 2] + lucas[i - 1]) % MOD;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int times, term;
	Initialize();
	while (ReadNumber(&term))
		printer->PrintNumber(*(lucas + term));
	delete printer;
}