FLOWGROW - Flower growing

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.


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)

hide comments
2012-08-04 20:42:19 Soumajyoti
Got an AC!!:)
2009-10-10 18:12:43 anshuman mishra
is k = 0 possible?
plz reply
2009-09-10 16:19:19 Drew Saltarelli
what happened to "please don't make problems with time limits of less than 0.5s" ? -.-
2009-07-25 14:25:34 :D
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.
2009-06-08 16:25:00 piyifan
I use an algorithm with time complexity O(logm+logn*(7^3)+k) got TLE.
Have somebody used it AC?
2009-06-08 16:25:00 [Trichromatic] XilinX
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
2009-06-08 16:25:00 .:: Pratik ::.
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
2009-06-08 16:25:00 AnhDQ
right :-) Time limit is too easy for all ;-) enjoy!
2009-06-08 16:25:00 Robert Gerbicz
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
2009-06-08 16:25:00 .:: Pratik ::.
Time limit is super-strict :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.