SPOJ.com - Problem FLOWGROW

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 ≤ 10¹⁵.
- The number of lines in Input does not exceed 5000.

Submit solution!

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 :(

Submit solution!

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)