Vì đang chán, Dế Mèn đã rủ Mondeus chơi trò chơi sau: Dế Mèn sẽ chọn một số nguyên không âm ~S~ và sau đó Mondeus sẽ chọn ra 3 số nguyên không âm ~(a, b, c)~ sao cho ~a + b + c = S~. Mỗi lượt chơi, người chơi sẽ chọn một số nguyên dương ~k~, tăng 1 số trong bộ ~(a, b, c)~ lên ~k~ và giảm 2 số còn lại đi ~k~. Dế Mèn là người đi trước.

Một người chơi được xem là thua nếu người chơi đó không thể chọn được số nguyên dương ~k~ nào sao cho sau lượt chơi của mình thì ~\min(a, b, c) \ge 0~. Vì hai bạn rất thông minh nên luôn chơi tối ưu. Biết số ~S~ mà Dế Mèn đã chọn, các bạn hãy giúp Mondeus đếm xem có bao nhiêu bộ ba ~(a, b, c)~ mà Mondeus có thể chọn để giành chiến thắng nhé.

Dữ liệu

Dòng đầu tiên chứa một số nguyên không âm ~S~ ~(S \le 10^9)~.

Kết quả

In ra số cách chọn bộ ba ~(a, b, c)~. Vì đáp án có thể rất lớn nên hãy in ra phần dư của đáp án với phép chia ~10^9 + 7~.

Ví dụ

Sample Input 1

0

Sample Output 1

1

Sample Input 2

1

Sample Output 2

3

Sample Input 3

3

Sample Output 3

9

Giải thích

• Với ~S = 0~, chỉ có một bộ thỏa mãn là ~(0, 0, 0)~.

• Với ~S = 1~, có ~3~ bộ thỏa mãn là ~(0, 0, 1), (0, 1, 0), (1, 0, 0)~.

Chấm điểm

Bài chỉ có duy nhất một subtask.