Em Phú phá phách vừa mới lớn nên đã bắt đầu tập tành xếp hình. Đây là một trò chơi giải trí lành mạnh rất kích thích phát triển tư duy. Em đã bắt đầu với các quân domino (gồm ~2~ ô vuông ghép lại), rồi tromino (gồm ~3~ ô vuông ghép lại). Hôm nay, em bắt đầu chơi với level cao hơn là tetromino gồm ~4~ ô vuông ghép lại. Chị gái mua cho em nhiều mảnh ghép có dạng tetromino (mỗi mảnh có số lượng tùy ý). Em Phú bèn lấy áo dài của chị để cắt ra thành một hình chữ nhật ~2 \times n~ để xếp lên đó cho dễ. Em đang thắc mắc là có bao nhiêu cách xếp khác nhau với các quân tetromino này để có thể phủ kín được mảnh áo dài của chị mình? Hai cách lát được xem là khác nhau nếu dùng các loại tetromino khác nhau hoặc thứ tự sắp xếp của chúng là khác nhau.

Input:

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output:

Đáp số của bài toán. Vì đáp số có thể rất lớn nên lấy modulo ~10^9+7~.

Sample input 1:

1

Sample output 1:

0

Sample input 2:

2

Sample output 2:

1

Sample input 3:

2022

Sample output 3:

12973685

Giải thích: ta thấy với ~n=1~ thì nền nhà chỉ có ~2~ ô gạch, không thể lát được, còn với ~n=2~, ta thấy nền nhà có kích thước ~2 \times 2~ nên có một cách duy nhất là dùng hình vuông.