As Macduff dries himself off, he sluggishly follows Macbeth into yet another portal. Macduff is exhausted after counting a hundred thousand door numbers, getting hit by literally a million daggers, and answering another million questions about range sums. Honestly, Macduff is starting to question whether it's even worth getting revenge for his egged family.

He finds himself in a Wild West saloon, with cowboys, bandits, barrels and revolvers. Macbeth begins announcing his next trap for Macduff:

Macduff, I've got you trapped now! For your next task, you must predict the result of a revolver duel between cowboys and bandits! Initially, there are ~N~ and ~M~ cowboys and bandits lined up in a circle! Bandits and cowboys will fire pellets at each other, and anyone who is hit is out! Cowboys always fire at integer seconds, but bandits fire at ~T + 0.5~ seconds (i.e. in between two integer seconds), except for blue bandits, who fire only after they've been hit once! That's right, there are different colors of cowboys and bandits! Blue bandits are not out after being hit once; they have to be hit twice. Additionally, cowboys that are taller will be hit by bandits at most 2 positions away from them, while shorter cowboys (but only red ones, not blue ones), will be hit by bandits at most 1 position away! Also, cowboys with square hats (but only blue ones, not red ones) will appear as purple after being hit by a blue bandit, while bandits with circular hats (but only tall ones that are red), will fire (if they are blue, at ~T + 0.5~ seconds and integer seconds) fire a bouncy pellet that only hits short, red cowboys wearing triangular hats, only at ~T + 0.5~ seconds, and they turn green and their hats become square after being hit by a non-bouncy pellet. Furthermore, cowboys that-

Here, Macduff raises his hand to interrupt Macbeth. Macbeth, thinking that this is a challenge, declares:

Thou losest labor.

As easy mayst thou the intrenchant air

With thy keen sword impress as make me bleed.

Let fall thy blade on vulnerable crests;

I bear a charmèd life, which must not yield

To one of woman born!

But, no, Macduff is just really, really, exhausted. He turns away from Macbeth and casually walks over to the bartender to get a glass of milk, tuning out Macbeth's passionate and relentless soliloquy.

Macduff is about to take a seat when the bartender stops him. The bartender says:

This bar has ~N~ seats in a row. You may sit in any non-occupied seat, but know this: the cowboys and bandits in this town are rather shy. They would always prefer to sit in seats that are not adjacent to another occupied seat. We'll call those types of non-occupied seats that are free on both sides good seats. If a cowboy / bandit walks into the bar and sees that there are no good seats, they will simply go home. Otherwise, they will choose a good seat at random and sit there.

Now, the bartender offers Macduff a deal:

Y'know, depending on where each customer picks to sit, there may be enough space for many or few customers in total. I tell you what: If you can tell me the minimum and maximum number of cowboys / bandits that may sit in these seats in an arrangement such that there are no more good seats (i.e. any additional cowboys / bandits that walk in will just go home), I'll let you have a free glass of milk.

Then, the bartender ponders for a few more seconds and adds:

Actually, I want you to also tell me the number of ways that the minimum / maximum number of customers can arrange themselves such that they take up all good seats. Two arrangements are considered different if there is one spot that is occupied in one but not occupied in another.

Macduff is definitely not in the mood for another puzzle, but he decides that for a free glass of milk, this is worth it.

Input Specification

On the first line, there is just one integer, ~N~, the number of seats.

Output Specification

On one line, output four space-separated integers, ~W~, ~X~, ~Y~, and ~Z~.

~W~ represents the minimum number of customers that can fill up all good seats.

~X~ represents the maximum number of customers that can fill up all good seats.

~Y~ represents the number of ways that ~W~ customers can fill up all good seats.

~Z~ represents the number of ways that ~X~ customers can fill up all good seats.

Constraints

Subtask 1 [50%]

~5 \le N \le 100~

Subtask 2 [50%]

~5 \le N \le 10^{9}~

Sample Input 1

10

Sample Output 1

4 5 10 2

Sample Explanation 1

Let an empty seat be denoted as . and an occupied seat denoted as #.

Here are the 10 possible ways for 4 customers to take up all good seats:

#.#..#..#.

#..#.#..#.

#..#..#.#.

#..#..#..#

.#.#.#..#.

.#.#..#.#.

.#.#..#..#

.#..#.#.#.

.#..#.#..#

.#..#..#.#

Here are the 2 possible ways for 5 customers to take up all good seats:

#.#.#.#.#.

.#.#.#.#.#