New Restaurant

Problem code: NEWREST

All submissions for this problem are available.

Chef Dengklek will open a new restaurant in the city. The restaurant will be open for N days. He can cook M different types of dish. He would like to cook a single dish every day, such that for the entire N days, he only cook at most K distinct types of dishes.

In how many ways can he do that?

Input

The first line contains a single integer T, the number of test cases. T test cases follow. Each test case consists of a single line consisting of three integers N, M, K.

Output

For each test case, output a single line consisting the number of different ways he can cook for the entire N days, modulo 1000000007.

Constraints

  • 1 ? T ? 100
  • 1 ? N ? 1000
  • 1 ? M ? 1000000
  • 1 ? K ? 1000

Example

Input:

4
1 1 1
2 2 2
4 3 2
5 7 3

Output:

1
4
45
5887

Author: fushar
Date Added: 6-09-2011
Time Limit: 2 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, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Can anybody explain the 3rd

phantom11 @ 1 Nov 2011 07:20 PM
Can anybody explain the 3rd test case

what exactly do want to be

jelu @ 1 Nov 2011 10:01 PM
what exactly do want to be explained?

@jelu as to how the the

phantom11 @ 1 Nov 2011 11:33 PM
@jelu as to how the the answer turns out to be 45

@ phantom11: we're sorry we

fushar @ 2 Nov 2011 03:18 PM
@ phantom11: we're sorry we can't. It is supposed to be discovered by the contestants themselves.

is k always less than M

rijulaggarwal @ 2 Nov 2011 04:16 PM
is k always less than M

yes

k1ps @ 3 Nov 2011 04:53 PM
yes

@admin-my code gives me

digo @ 4 Nov 2011 06:17 AM
@admin-my code gives me instant answers(well within 2 sec) for the max test case limits on my machine, but the judge gives tle,any idea about whats happening?

I can never view the my

_arjun @ 4 Nov 2011 08:55 PM
I can never view the my submissions page for any problem, this is very annoying each time I have to see my past solutions I have to search them in "All Submission page". Please do reply.

judge gives me wrong

pkvprakash_86 @ 4 Nov 2011 10:55 PM
judge gives me wrong answer. Can you provide answer for test case 1000 1000000 1000 ?

also can you provide me the

pkvprakash_86 @ 4 Nov 2011 11:05 PM
also can you provide me the answer for 3 7 5?

No, we cannot provide any

fushar @ 5 Nov 2011 07:06 AM
No, we cannot provide any test case. Remember, this is a contest.

The question reads "at most K

garggaurav1995 @ 5 Nov 2011 11:22 AM
The question reads "at most K distinct types". In that case, the third test case has 48 possibilities. Admin Please check.

@ garggaurav1995 No, it has

fushar @ 5 Nov 2011 02:54 PM
@ garggaurav1995 No, it has 45 possibilities. The test cases are correct.

@ bravo_g7: If it is stupid,

fushar @ 6 Nov 2011 08:16 AM
@ bravo_g7: If it is stupid, then you should have solved it (have you?). By the way, I assure you that to solve this problem you require much knowledge about computer science.

I am getting Run Time

narrow001 @ 6 Nov 2011 10:50 AM
I am getting Run Time error...though program is working on my computer...Pls help me out.. can you pls suggest the situation in which run time error comes..

PLEASE any body explain 3rd

selfcompiler @ 6 Nov 2011 01:49 PM
PLEASE any body explain 3rd case..........

Does the 3rd test case

garggaurav1995 @ 6 Nov 2011 01:53 PM
Does the 3rd test case include the possibility of serving the same dish for all 4 days?

@ garggaurav1995: Yes.

fushar @ 6 Nov 2011 03:13 PM
@ garggaurav1995: Yes.

@ narrow001: No suggestion is

fushar @ 6 Nov 2011 03:14 PM
@ narrow001: No suggestion is allowed during the contest.

[edited by admin] please do

theicebreaker @ 6 Nov 2011 08:43 PM
[edited by admin] please do not post additional test cases

my code is working fine for

studd @ 8 Nov 2011 05:49 PM
my code is working fine for the testcases and my alogrithm is perfect but i am getting runtime error....Can any one point me out to a reading about how to remove runtime errors and why they are caused. A little help would be nice

i want to ask

mohitsdesire @ 8 Nov 2011 08:58 PM
i want to ask that...restaurant is open for 5 days and chef only know 3 dishes then.. can her repeat any two for rest 2 days ?

I want to ask

mohitsdesire @ 8 Nov 2011 08:58 PM
I want to ask that...restaurant is open for 5 days and chef only know 3 dishes then.. can he/she repeat any two for rest 2 days ?

:( :( :( Am I that bad?? :(

rajneesh2k10 @ 9 Nov 2011 12:19 PM
:( :( :( Am I that bad?? :(

@Admin..............time

satya_patel @ 10 Nov 2011 03:34 AM
@Admin..............time given is for all 100 test cases or for one test test case...............b'cause my solution is run under 1 sec for maximum test case and for all test case sure take more than 2 sec..............and i m getting TLE

@satya_patel - time given is

shettynamit @ 10 Nov 2011 10:38 AM
@satya_patel - time given is for all 100 test cases

Nice problem :)..The time

ritesh_gupta @ 10 Nov 2011 10:33 PM
Nice problem :)..The time limit was quite strict indeed.......

seems really hard

cyberax @ 11 Nov 2011 02:44 AM
seems really hard (impossible?) to do it in Python. i tried almost the same code in C, and got AC.

I tried to do it in Python

cupidvogel @ 11 Nov 2011 03:33 PM
I tried to do it in Python too, and the code took only 20 lines, but I got a runtime error. I can't think of a formula except Inclusion-Exclusion principle, and that requires calculation of factorials of large numbers, and that was taking an awful amount of time.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions