FLOWGROW - Flower growing

no tags 

The farmer AnhDQ grows flower in his MxN garden (M rows and N columns). He wants to grow flower satisfying that: Each row of the garden has at least k color(s) of flower; and he has 7 types of flower: red, orange, yellow, green, blue, indigo, and violet to use.

Request

Count the number of ways to grow flower on his garden.

Input

- Contains several lines, there are three number M, N, k on each.

Output

- Contains the answer for each line of Input, mod 2370823708, written on separate lines.

Example

Input:
1 7 7

Output:
5040

Limitations

- 1 ≤ M, N ≤ 1015.
- The number of lines in Input does not exceed 5000.


hide comments
Soumajyoti: 2012-08-04 20:42:19

Got an AC!!:)

anshuman mishra: 2009-10-10 18:12:43

is k = 0 possible?
plz reply

Drew Saltarelli: 2009-09-10 16:19:19

what happened to "please don't make problems with time limits of less than 0.5s" ? -.-

:D: 2009-07-25 14:25:34

Hint for people with TLE: the modulu operation of obviusly the main problem. You don't have to do modulo after every operation, think how to minimaze it.

piyifan: 2009-06-08 16:25:00

I use an algorithm with time complexity O(logm+logn*(7^3)+k) got TLE.
Have somebody used it AC?

[Trichromatic] XilinX: 2009-06-08 16:25:00

Mmm. Time limit is very strict for an algorithm with time complexity O(logm+logn*(7^3)+k). (Although I have used this and get AC.)

Last edit: 2009-06-07 12:38:51
.:: Pratik ::.: 2009-06-08 16:25:00

I have an O( k + log M ) algorithm, but I think the mod operations are quite expensive, I think if the complexity isnt any better, there is no point of optimising it to the brink, not all of us are qualified to do that :P
I have improved my I/O too, besides this is too much biased for C++ people, what if somebody decides to write in Java.

Just a question, is k <= 7 ,
if not so my solution is super-slow :)

Re: "quite expensive", but not very ;) so try to find a way to improve your execution time, several ones got AC with SUPER time :)

Last edit: 2009-06-08 00:36:16
AnhDQ: 2009-06-08 16:25:00

right :-) Time limit is too easy for all ;-) enjoy!

Robert Gerbicz: 2009-06-08 16:25:00

Or your code is super-slow :)
I've checked on Vietnamese site the same problem has already solved by 5 peoples (including me), the fastest is my: 0.16 sec. The slowest is 1.15 sec.

Last edit: 2009-06-05 19:11:46
.:: Pratik ::.: 2009-06-08 16:25:00

Time limit is super-strict :(


Added by:AnhDQ
Date:2009-06-05
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Mr Tuan Khuc Anh - NTU (Singapore)