Word Counting

Problem code: WCOUNT

All Submissions

All submissions for this problem are available.

Chef has decided to retire and settle near a peaceful beach. He had always been interested in literature & linguistics. Now when he has leisure time, he plans to read a lot of novels and understand structure of languages. Today he has decided to learn a difficult language called Smeagolese. Smeagolese is an exotic language whose alphabet is lowercase and uppercase roman letters. Also every word on this alphabet is a meaningful word in Smeagolese. Chef, we all know is a fierce learner - he has given himself a tough exercise. He has taken a word and wants to determine all possible anagrams of the word which mean something in Smeagolese. Can you help him ?

Input

Input begins with a single integer T, denoting the number of test cases. After that T lines follow each containing a single string S - the word chef has chosen. You can assume that 1 <= T <= 500 and 1 <= |S| <= 500. You can also assume that no character repeats more than 10 times in the string.

Output

Output one line per test case - the number of different words that are anagrams of the word that chef has chosen. As answer can get huge, print it modulo 10^9 + 7

Example

Input:
4
ab
aa
aA
AAbaz

Output:
2
1
2
60

Description: In first case "ab" & "ba" are two different words. In third case, note that A & a are different alphabets and hence "Aa" & "aA" are different words.

Author:	yellow_agony
Tester:	anton_lunyov
Editorial	http://discuss.codechef.com/problems/WCOUNT
Date Added:	17-01-2012
Time Limit:	3 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Submit

Comments

Login or Register to post a comment.

why i am keep getting RE. my

bristy @ 1 Feb 2012 05:37 PM

why i am keep getting RE. my prog is working correctly on my m/c..

Same here ... SIGFPE is RE

maxcoder @ 1 Feb 2012 07:45 PM

Same here ... SIGFPE is RE that I'm getting.

same here.........

donald5508 @ 1 Feb 2012 07:56 PM

same here.........

me too... it's giving wrong

elmagnifico @ 1 Feb 2012 08:12 PM

me too... it's giving wrong answer but on my pc i tried almost 50 different words... All gave correct answers....

Please read our FAQ:

admin @ 1 Feb 2012 08:17 PM

Please read our FAQ: http://www.codechef.com/wiki/faq#Why_do_I_get_a_SIGFPE

I am also getting RE

deepinhacking @ 1 Feb 2012 09:12 PM

I am also getting RE

@darkdiver. There are 26

anton_adm @ 2 Feb 2012 01:27 AM

@darkdiver. There are 26 Roman letters. So the upper bound from here is 520 and 500 is independent bound.

Does modulo 10^9 +7 mean (x

debjitbis08 @ 2 Feb 2012 01:58 AM

Does modulo 10^9 +7 mean (x modulo (10^9 +7)) or (x modulo (10^9) + 7)?

modulo 10^9 +7 will mean (x

wrongnumber @ 2 Feb 2012 02:10 AM

modulo 10^9 +7 will mean (x mod 1000000007)

can you provide some test

richi18007 @ 2 Feb 2012 03:26 AM

can you provide some test cases , it is WA and I have tried a lot of test cases and my code gives correct answer on them

i think runtime errors are

juahn31 @ 2 Feb 2012 05:38 AM

i think runtime errors are due to so big inputs, i also get run time error

any sorts of word are always

yosuke_fujii @ 2 Feb 2012 06:39 AM

any sorts of word are always meaningful word of Smeagolese, aren't them? i write code which can always return correct answer in this understanding, but i received WA... (of course i pay attention to same letter and correct all of example case :( )

@debjitbis08 : It means : x

nikhil_adm @ 2 Feb 2012 10:10 AM

@debjitbis08 : It means : x modulo (10^9 + 7)

@yosuke_fuji : Yes, all words

nikhil_adm @ 2 Feb 2012 10:11 AM

@yosuke_fuji : Yes, all words are always meaningful in Smeagolese. You'd have to find out the bug in your algorithm/program yourself, we can't help you there.

The input does not contain

mvivek241 @ 2 Feb 2012 11:03 AM

The input does not contain spaces, right? And can you provide 1 or 2 larger inputs and their expected outputs, i want to check if my program works.

String will contain only

anshuavi @ 2 Feb 2012 05:55 PM

String will contain only alphabets and no other special characters,right?

i cannot submit my

vamsi2708 @ 2 Feb 2012 05:57 PM

i cannot submit my answer. language field is required. you cannot do in this language. these are displaying when i submit my answer. can anybody help me out from this problem?

Can answer exist in floating

cooltodinesh @ 2 Feb 2012 07:17 PM

Can answer exist in floating point??

Can any of the test case be

codeit @ 3 Feb 2012 02:04 AM

Can any of the test case be blank? Or can there be space in the input strings?

@gspinner not correct..

timegone @ 3 Feb 2012 02:10 AM

@gspinner not correct..

@cooltodinesh the output must

cracker2excel @ 3 Feb 2012 09:50 AM

@cooltodinesh the output must be an integer

1 amjjdsjnnsakjkdass 67334369

anubhawraj @ 3 Feb 2012 11:43 AM

1 amjjdsjnnsakjkdass 67334369 is the output correct..? somebody who got AC please tell.....

@timegone plz answer:1

anubhawraj @ 3 Feb 2012 11:44 AM

@timegone plz answer:1 amjjdsjnnsakjkdass 67334369 is the output correct..? somebody who got AC please tell.....

same here... :(

neo0057 @ 3 Feb 2012 06:31 PM

same here... :(

Discussing solutions,

nikhil_adm @ 3 Feb 2012 08:55 PM

Discussing solutions, algorithms or particular test cases is strictly prohibhited and violation of this rule may invite direct disqualification. Please refrain from posting programs or test data here.

@nikhil_adm you should give

crazycoder_sns @ 4 Feb 2012 12:21 AM

@nikhil_adm you should give some test cases in each problem for better understanding.....:-p

The last sample test case

calc_saransh @ 4 Feb 2012 03:57 AM

The last sample test case clearly defines the problem if the problem statement was even a little unclear.

my code showing ans in no

sachdeva @ 4 Feb 2012 12:43 PM

my code showing ans in no time in my system even for |S|=500... but here i am getting TLE... how is that possible.??

here the character set is a-z

s1a3 @ 4 Feb 2012 02:58 PM

here the character set is a-z and A-Z, isn't it?

@admin m facing th same prob

nnimish19 @ 4 Feb 2012 03:11 PM

@admin m facing th same prob as @sachdeva

@admin im gettin NZEC error

daryllopes89 @ 4 Feb 2012 05:43 PM

@admin im gettin NZEC error while at my machine the code gets executed properly plz hlp

@admin now even im facin the

daryllopes89 @ 4 Feb 2012 06:34 PM

@admin now even im facin the same problem as @sachdeva

any completed experts plz

rijin @ 4 Feb 2012 10:22 PM

any completed experts plz tell ans for "amjjdsjnnsakjkdass" ...

@admin: can u tell me plz why

saurabhskj @ 5 Feb 2012 02:19 AM

@admin: can u tell me plz why i am getting the wrong answer???

what should I use, lld or

darkstalker @ 5 Feb 2012 11:18 AM

what should I use, lld or I64d ?

I don't understand, I have

cupidvogel @ 6 Feb 2012 02:25 PM

I don't understand, I have checked my code with words 600 characters long, and that too with huge number of occurrences of two or three particular letters so that I can test it with large numbers (factorials), and there I am getting instantaneous results. How come here it is showing time limit exceeded?

@rijin, mY resuLt is

bodmas @ 6 Feb 2012 03:59 PM

@rijin, mY resuLt is 567334383. does tHat aGree witH yours?

@bodmas, Yeah, I had had the

cupidvogel @ 6 Feb 2012 04:23 PM

@bodmas, Yeah, I had had the same answer too for that string.

why i m getting runtime

minav90 @ 6 Feb 2012 05:33 PM

why i m getting runtime error(NZEC) but it runs fine on my pc with out any error..........

@admin please help i m

minav90 @ 6 Feb 2012 06:11 PM

@admin please help i m getting runtime(NZEC) error again again while it is running fine on my pc.

@admin: pls see to it y it is

sachdeva @ 6 Feb 2012 07:41 PM

@admin: pls see to it y it is showing TLE here, cos i m getting instantaneous results in my system..??

Come on, I tried my code with

cupidvogel @ 6 Feb 2012 08:04 PM

Come on, I tried my code with the most stringent string, that is a to z and A to Z each repeated 10 times, and I got the answer instantly. How come here it is showing time limit exceeded?

@admin: exactly sample prblm

savvy_fedex @ 6 Feb 2012 09:53 PM

@admin: exactly sample prblm as cupidvogel. Getting instant answers at ideone as well as my system. Still TLE. Doesn't make sense/

@admin i am getting runtime

evil1mind_79 @ 6 Feb 2012 10:23 PM

@admin i am getting runtime error(SIGFPE) but m not messing with any modulos or division operation.Kindly provide me a sample case for which its not working.

this is so frUstrating. I'vE

bodmas @ 7 Feb 2012 01:25 AM

this is so frUstrating. I'vE exAmined my solution over and over agaiN. I'M sure it's corRect yet I'm geTtinG WA. @admin, I don'T know wHat to do nOw, this is cRazy.

max length of string is

adityaork @ 7 Feb 2012 07:02 PM

max length of string is <=500...?? i read in comments......someone saying 520..??

I'm getting TLE. I looked up

irajvardhan @ 8 Feb 2012 11:42 PM

I'm getting TLE. I looked up the FAQ and as suggested used the "time ./out.txt" command. I got three different time results...'real' 'user' and 'system'. Which among these should be below the given time constraint?

this is so pathetic.i am

pratishgupta91 @ 9 Feb 2012 02:17 AM

this is so pathetic.i am getting wa..

@pratishgupta91::Be CareFul

ritesh_gupta @ 9 Feb 2012 01:46 PM

@pratishgupta91::Be CareFul with Overflow.Try to Handle the Datatype overflow,properly...I saw the judge (exclusively in this problem)gave wrong answer ,even if the program encounters datatype overflow,infact the judge should have actually display Runtime error in that case..

still WA....took care of

phoenix_shaan @ 9 Feb 2012 08:47 PM

still WA....took care of overflow though

@admin submitted the problem

rdaxxx @ 9 Feb 2012 11:05 PM

@admin submitted the problem at least 10 times and still wrong answer although checked by me on different-2 test condtion all are correct , please any one give me a better test condition to test on , plz help , any one ????????/

i submitted my solution, it

codetantra @ 11 Feb 2012 12:35 AM

i submitted my solution, it works, but on my PC it takes 5.7 secs (worst case scenario) and on codechef it takes 13.6 secs. is this expected?

SUCCESSFUL SUBMISSIONS

Fetching successful submissions

CodeChef is a non-commercial competitive programming community

In order to report copyright violations of any kind, send in an email to copyright@codechef.com

CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.

Site Navigation