It’s one of the boring days, and coach Ali decided to turn his TV on and to see something amusing, to his luck they were showing the famous Simpsons series, so he made popcorn and sat to watch it, the episode name was “Marge and Homer Turn a Couple Play” from 2006 season, the episode took part at a baseball court, in the big screen they asked the following multi-choice question:

Can you guess the number of the audience?? With answers:

• 8128
• 8191
• 8208
• I can’t guess.

“Numbers???” Shouted Coach Ali, “I wonder are they chosen randomly, or do they refer to something???” You know Simpsons and its weird symbols.

That made him curious so he decided to investigate it, as Ali always says: ”Google is stupid” He decided to use the Syrian search engine, Shamra.sy and Shamra gave him the answer in a blink of eye!!! and  guess what? Each of these numbers belong to a family of numbers!!!

• 8128 is called an “Ideal number” (expect to see a problem about this family.)
• 8191 is called a “prime number” (primes are well known to all.)
• 8208 is called a “Narcissistic number”.

As Coach Ali loves Greek Methodology he remembered the famous myth of god “Narcisse” so he decided to make extra search about this family, again Shamra gave him the answer in a blink of eye!!! According to Wikipedia: it is a number that is the sum of its own digits each raised to the power of the number of digits.

For example: 8208 = 8^4+2^4+0^4+8^4 = 4096+16+0+4096

Now Ali is wondering, how many positive Narcissistic numbers consisting of N digits??? As he is busy in studding for the expected “Principles of Electronics” test, he decided to give the problem to his contestants, as part of their training for coming TCPC 2016.

Input

One line, containing N,   1<=N<=8

Output

One line, containing the number of positive Narcissistic numbers consisting of N digits.

Example

Input:
1

Output:
9

Note: As Coach Ali is impatient, the time limit per test for every test case is just 0.1 Seconds.