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 và Dế Mèn sẽ 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 số nguyên dương k bất kỳ sao cho sau lượt chơi của mình thì min(a, b, c) \geq 0. Vì hai bạn rất thông minh nên luôn chơi tối ưu. Biết rằng Dế Mèn chọn số S, các bạn giúp Mondeus đếm xem có bao nhiêu bộ 3 (a, b, c) Mondeus có thể chọn để dành chiến thắng nhé.

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

In ra số cách chọn bộ 3 (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ới S = 0, chỉ có một bộ thỏa là : (0, 0, 0).
• Với S = 1, có 3 bộ thỏa là: (0, 0, 1), (0, 1, 0), (1, 0, 0).