Một nhà hàng bánh ngọt có 3 loại bánh: bánh táo, bánh xoài và bánh răng. Loan muốn đặt trước n chiếc bánh. Vì cô là một khách hàng kỹ tính nên muốn bữa ăn của mình thõa mãn thêm 2 điều kiện: số lượng bánh táo phải chia hết cho 2 và số lượng bánh xoài phải chia hết cho 3.

Loan sẽ thưởng thức từng chiếc bánh một. Hai cách thưởng thức bánh được coi là khác nhau nếu như chiếc bánh thứ \(i\) \((1 \leq i \leq n)\) Loan ăn là hai chiếc bánh khác nhau.
Ví dụ:

Cách thưởng thức 1: Loan ăn 2 bánh táo, 1 bánh răng, 3 bánh xoài

Cách thưởng thức 2: Loan ăn 2 bánh táo, 3 bánh xoài, 1 bánh răng

Vậy hai cách thưởng thức trên là khác nhau vì chiếc bánh thứ 3 mà Loan ăn ở cách thứ nhất là bánh răng, còn ở cách thứ hai là bánh xoài.

Input:

Một số nguyên dương \(n\) \((1 \leq n \leq 10^6)\), là số lượng bánh Loan đặt

Output:

Số lượng cách thưởng thức bánh khác nhau của Loan. Vì đây là một số rất lớn nên chỉ cần in ra kết quả sao khi chia lấy dư cho \(10^9 + 7\).

Ví dụ:

Input:

3

Output:

5

Input:

10

Output:

9882

Giải thích ví dụ:

Ở ví dụ thứ nhất, có 5 cách thưởng thức thỏa mãn: (Bánh răng, Bánh răng, Bánh răng), (Bánh xoài, Bánh xoài, Bánh xoài), (Bánh táo, Bánh táo, Bánh răng), (Bánh răng, Bánh táo, Bánh táo), (Bánh táo, Bánh răng, Bánh táo).