NNUM - One of the Simpsons symbols

no tags 

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.


hide comments
:D: 2016-10-01 00:36:19

Re Filip: "number of positive Narcissistic numbers"

HEMANT SANJAY HUSE: 2016-01-05 11:19:02

my 100th..

Filip Sollar: 2015-12-02 20:39:39

isn't there 10 narcistic numbers with 1 digit ? 0,1,2,3,4,5,6,7,8,9 ?

ALi Ibrahim: 2015-11-21 07:49:31

Alex Anderson Sometimes you have to use this method in contests, especially at ACM...

Alex Anderson: 2015-11-21 07:33:45

I don't like questions like this, because it is very easy to just precompute/look up the answer online, then hardcode the answers.

ALi Ibrahim: 2015-11-20 12:42:19

matematikaadit your welcome.

matematikaadit: 2015-11-20 12:36:36

edit: ok, thanks for fixing it.

Last edit: 2015-11-20 12:39:12
ALi Ibrahim: 2015-11-20 12:35:50

Since this is my first problem i write on Spoj, there was some troubles with the system, i am sorry for everyone who submitted an accepted code, but got WA, anyway now everything is Ok, you can resubmit your corrected codes :)


Added by:C137
Date:2015-11-20
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:own