FLOWGROW  Flower growing
English  Tiếng Việt 
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 ≤ 10^{15}.
 The number of lines in Input does not exceed 5000.
hide comments
Soumajyoti:
20120804 20:42:19
Got an AC!!:) 

anshuman mishra:
20091010 18:12:43
is k = 0 possible?


Drew Saltarelli:
20090910 16:19:19
what happened to "please don't make problems with time limits of less than 0.5s" ? . 

:D:
20090725 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:
20090608 16:25:00
I use an algorithm with time complexity O(logm+logn*(7^3)+k) got TLE.


[Trichromatic] XilinX:
20090608 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: 20090607 12:38:51 

.:: Pratik ::.:
20090608 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


AnhDQ:
20090608 16:25:00
right :) Time limit is too easy for all ;) enjoy! 

Robert Gerbicz:
20090608 16:25:00
Or your code is superslow :)


.:: Pratik ::.:
20090608 16:25:00
Time limit is superstrict :( 
Added by:  AnhDQ 
Date:  20090605 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Mr Tuan Khuc Anh  NTU (Singapore) 