Vào dịp Tết sum vầy, sau khi nhận được khá nhiều tiền lì xì Phúc quyết định tổ chức bầu cua cho các em nhỏ trong nhà chơi. Và muốn các em nhỏ nhân đôi niềm vui, Phúc đã quyết định gấp đôi phần thưởng lên. Tuy nhiên vì không muốn các em "thua nhiều" sẽ buồn nên Phúc ra luật là chỉ được đặt ~1~ xu mỗi lượt chơi. Vì thế khi thắng các em sẽ nhận được tận ~2~ xu và khi thua thì các em chỉ mất duy nhất ~1~ xu.

Ngửi được mùi "kèo thơm" Nhã là bạn thân của Phúc đã nhanh chóng nhập tiệc góp vui. Tuy nhiên khi sắp tham gia Nhã lại quay xe và nghĩ rằng "nếu mình ăn thì Phúc làm gì còn có tiền lì xì cho các em nhỏ, còn nếu mình thua thì mất mặt trước các em lắm huhu. Phải làm sao, phải làm sao? Hay là tự đặt thử thách cho bản thân tìm cách làm thế nào để huề vốn đi hehe."

Hãy giúp Nhã tính xem có bao nhiêu trường hợp để Nhã huề vốn.

Input

Duy nhất ~1~ số nguyên dương ~n~ ~(1 \le n \le 10^6 )~ là số ván chơi.

Output

Duy nhất ~1~ số nguyên là số trường hợp Nhã huề vốn. Tuy nhiên đáp án rất lớn nên hãy lấy kết quả là phần dư của phép chia cho ~04022004~.

Simple Input

3

Simple Output

3

Giải thích test đề:

Các trường hợp mà Nhã huề vốn là:

• Thua - Thua - Thắng.
• Thua - Thắng - Thua.
• Thắng - Thua - Thua.

Cách tính điểm:

• ~30 \%~ test có ~n \le 20~.
• ~40 \%~ test có ~n \le 10^3~.
• ~30 \%~ test có ~n \le 10^6~.