beecrowd | 2955

Truuuuuco!

By Samuel Eduardo da Silva, IFSULDEMINAS/UFF BR Brazil

Timelimit: 1

No one has ever done this, but it is intuitive to say that Computer Science and Computer Science courses hold the greatest legends of the traditional Truco game. The computer people love this game so much that over the years they have been proposing new rules and new scoring systems to make the game ever more challenging.

We will not go into the details of the rules of the game, firstly because everyone should know, given the niche of this test; secondly that for this problem, we are not interested in the rules, but in the scoring system.

The game is done in rounds, and the team that reaches or exceeds X points wins (archaically they were 12 or 15 points, but over time they have made the trick a more dynamic experience). In each round, a team can win 1 or a multiple amount of 3 in points (the famous shouting).

If it is not necessary to "chew", that is, only 1 point is left to win, it is forbidden to chew. Universal rule, do not question.

Remember that if the multiple of 3 of the trick is greater than or equal to the remainder of the points to win the game, it is not necessary for the opponent to increase it more. (A lot of people like to continue screaming, even though it does not make sense, but here we have civilized and intelligent people).

It is also considered that a person won perfectly, when he can reach exactly the number of points, without going over.

Josh Homme is a freshman on the computer course and wants to get his hands on the trick. He already knows programming and wants to create a program that gives the number of points to win, indicate how many possibilities there are to win (reach X points or exceed) and the minimum number of rounds to win in a perfect way.

Input

The entry contains an integer X(1 < X ≤ 1000), indicating the number of points required to win the game.

Limits: 1 <X ≤ 1000.

Output

The output contains two integers, indicating the number of chances to win and the minimum number of rounds for Josh to win the game perfectly.

Detail: The number of possibilities can be very large, so one must show the value that this number would leave of rest when being divided by 109 + 7.

Input Samples Output Samples

2

2 2

15

664 1

82

123888505 2