Statistics

Problem Statement

Manao is conducting an experiment to measure the humidity level of some spongy material. The experiment is conducted in a closed room which is observed from a side, so we will consider it in two dimensions.

The room is N centimeters wide. There are N drop counters built in the ceiling of the room. Drop counter 0 is attached 0.5 centimeters from the left end of the room, and each next one is attached 1 centimeter to the right of the previous one. You are given a String[] intensity filled with digits. Concatenate its elements to obtain one String S of length N. The i-th (0-based index) drop counter drips exactly S[i] drops per minute, where S[i] is the digit at the i-th position in S.

Manao is going to place M sponges in the room. All sponges are exactly L centimeters long and their thickness is negligible. Each sponge must be placed horizontally, it must be entirely within the room, and the distance between the left wall of the room and the sponge must be an integer. In other words, the coordinate of its left end must be an integer between 0 and N-L, inclusive. Different sponges must be attached at different heights. Each sponge will totally absorb every drop that drips at it. For example, in the following picture, the sponges (from top to bottom) absorb 12, 5, and 3 drops per minute.


The experiment requires the sponges to be attached in such a way that each of them absorbs between A and B drops per minute, inclusive. Manao is interested in the number of ways in which this can be done. Two ways P and Q of attaching the sponges are the same if and only if for each sponge S1 in P there exists a sponge S2 in Q such that S1 and S2 lie directly beneath the same sets of drop counters. A sponge X lies directly beneath a drop counter Y if there is no other sponge between them. That is, if there is some water dripping from the drop counter Y, it all lands on the sponge X. Note that according to these definitions the sponges are indistinguishable.

You are given the String[] intensity and the ints M, L, A, and B. Count the number of different ways to attach the sponges and return that count modulo 1,000,000,009.

Definition

Class:

TheExperiment

Method:

countPlacements

Parameters:

String[], int, int, int, int

Returns:

int

Method signature:

int countPlacements(String[] intensity, int M, int L, int A, int B)

(be sure your method is public)

Constraints

• intensity will contain between 1 and 6 elements, inclusive.
• Each element of intensity will be between 1 and 50 characters long, inclusive.
• Each element of intensity will consist of digits ('0'-'9') only.
• M will be between 1 and 300, inclusive.
• L will be between 1 and N, inclusive, where N is the total number of characters in intensity.
• A will be between 1 and 2700, inclusive.
• B will be between A and 2700, inclusive.

Examples

1. {"341156"}

   3

   3

   6

   10

   Returns: 2

   Manao needs to place three sponges of length 3 in such a way that they absorb between 6 and 10 drops per minute. The valid ways to attach the sponges are the following: In the first way, the sponges receive 8, 6 and 6 drops, from highest to lowest. In the second way, they absorb 7, 7 and 6. Note that Manao could interchange the heights of the lower two sponges in the second picture, but this would result in the same way.

2. {"999112999"}

   2

   4

   21

   30

   Returns: 2

   One of the platforms should have its left end exactly at the left wall. The other's left end can be either 4 or 5 centimeters away from the left wall.

3. {"111"}

   2

   2

   2

   3

   Returns: 0

   One of the platforms will never receive enough drops.

4. {"59059", "110", "1132230231"}

   1

   5

   10

   20

   Returns: 6

5. {"111111111111111111111111", "111111111111111111111111111", "11111111111111111111111"}

   12

   8

   4

   2700

   Returns: 418629948

6. {"1420211609787","047904","9","5"}

   4

   3

   3

   13

   Returns: 686

7. {"67878049026","8129","899553805"}

   3

   3

   12

   20

   Returns: 201

8. {"0965692189599","48","9","3"}

   3

   3

   40

   46

   Returns: 0

9. {"2469","8254870617490","197"}

   3

   3

   26

   36

   Returns: 0

10. {"30052012","36789432675670"}

    5

    2

    5

    6

    Returns: 1

11. {"5","373533547604","261709","04"}

    5

    3

    2

    10

    Returns: 230

12. {"127683309976","174","40"}

    3

    3

    23

    26

    Returns: 0

13. {"4006984650","8908503","191"}

    5

    3

    1

    8

    Returns: 8

14. {"275261381980928309422"}

    4

    3

    13

    20

    Returns: 53

15. {"88949553710676480"}

    5

    2

    8

    12

    Returns: 4

16. {"1844529665480001764462079070632811751","981385293555390168279058894765902851122932708463","9671791377712562302934673992658170","00345477649908818990768899692808276703695688652019","9505915771757753389976099922344500389448849281374","90730251143294396261954877023976468068327274408228"}

    30

    3

    10

    12

    Returns: 243767594

17. {"8346233266657155183270618483817008260501703","5289470541187559589085064918139546965658426967733","2463967434975435174543188325310467547294149386","247028390588710368912029476905730679982953248","06355702584589339534685282976756811921746160763652","99761980913302459717720204707586380150279743699321"}

    45

    4

    20

    57

    Returns: 92906453

18. {"9893670991470349676556040390488518121488146530","85162072905154460466073181488080192288857599079596","0691340871532530075037271368343433838797335372066","05843272220625630742876655514075561422315993385931","34652913789287581450907038776558809860736814475419","111032205392600771435462707528243817343579768"}

    41

    2

    10

    47

    Returns: 855060786

19. {"3458091612061975825590732687838514975650074770","209490955051208790897742050004560529332232605000","36366112091150249524351488810733691000760360550183","74656313501432120026321609848664648178891836083619","8546519623479745380923803466333889461109971933551","36449375498810145592887547757883463521976938270158"}

    41

    6

    23

    40

    Returns: 78010236

20. {"02359574287205107336582438780327899061753770","13227786614241738528236100289244830299659305931","93001087562166175375079000720871141437555637013588","41505145970455809623588978934575775584466211753246","83145273395756220773939905600499659091228601529915","85785801472518563552216500779417209801161824075300"}

    20

    4

    21

    101

    Returns: 507495157

21. {"289786925110426851555","35237424834623608250882595380515231032462434620","7764940511380650173998060467353906144167242754176","6568291015394651206486202937848795605127263514977","40636036185052552450254370497088762963700818599503","90047666794106598322416137647374986793662750450209"}

    23

    10

    34

    49

    Returns: 216609348

22. {"62459965057077622354729367106166560851948042004044","4376309863234174761284003511848677137668125887632","21690871286390595237092787076645542850954799354110","65953561701486187731109719628471073706626553022813","67205056028190169309634407441218927857776640680661","20824313828729457356402766687019118940940548562733"}

    46

    6

    1

    24

    Returns: 670102669

23. {"7954272676338942850344709407040983126308","9384233694011843214672989235300296102482391373441","82026413720852821101954780565007613069313102007207","19546196796410563359702575696515655224915258707819","67803399474799353422414936976958776137899422527129","59056599536902587322741504348280580239969180890818"}

    41

    9

    26

    47

    Returns: 99060230

24. {"787236023241570089822771938","929644545771235639798323472554005105998840730","6605227578706584557961146297772255651974590439292","54719405489018810322420964340209670774106812122944","78211465548952119099251526778306692258405077039800","15792166207852599366711678743865782876850890213396"}

    50

    2

    14

    53

    Returns: 0

25. {"493982823079504959341038704345819296610171874","97788180334352626615852490440812729807410224288","36662124851134508104150029281172870364333417095854","619379994173814682200362335239368011176596255776","0910174708659871178484068573302146683732111848775","0711675823469062393999999191308917137955498977283"}

    35

    3

    18

    40

    Returns: 777817650

26. {"104651245053434419786154925292028401481262966914","27993528864924973096387440822273631007401507433396","94416369332693266401964179506487751893061105090441","13820709899248539020634860977848540067023137558490","61242915574027599345381710369842332344033374825163","13384305007040751415904266349677940125785219634786"}

    43

    8

    16

    43

    Returns: 640184803

27. {"3327190451217021410778608705827876358617","7502610786442711660428047467929377330344","3245176705722857114666172592543858485546304726","084748707085709086742521195731095155627836923274","077872888070029065461583805184917300","4176529819218832565985297157696178354375053591868"}

    26

    7

    37

    74

    Returns: 0

28. {"04009497889551622058211663266025740","98096665811231527401224394705936587863929473980","44900813222049318525436493251055817829007531593431","33593274211176556873838489760755612940053952894566","25098850571065127410857054028580531704977778097699","55079015912672402365638159141310477874010749523593"}

    44

    9

    3

    26

    Returns: 592678821

29. {"4665661051523226781018512891360563487954632","179579461177176489490643238349494357425405174974","56058241256235439234422246498121637181922250923177","16162354447751259391103849068943810579044349268689","05816028481122663889109639995438319426018465216004","45282790883826050948269025781771488527476379094139"}

    44

    10

    6

    36

    Returns: 242748614

30. {"33060069826947006952544509577977348","57075118085183616112672797634260014333010792","932073273533013415614858855002077475","16660414056070803642998242799544554929884164","4103938016428374928175673915696851131733258713078","39981001861804133209696897873885929359303755006"}

    24

    10

    10

    17

    Returns: 6214160

31. {"69706219687196119346901601883802245502808294","9991380426929543363282377635324911918100384288559","72870441944629747690692749570651257490879515541050","41187102489121506513638874283061665915280083563957","58586738757533777682430131354278537610543109194679","19198631283420944705336233701930894301062737750652"}

    38

    4

    20

    61

    Returns: 16146554

32. {"90078649386977004446714458389072741197053","948022459147262037383907255201","906737390750556399209553677849661","37987157108263658842485937022155766145225075605432","93438828632679715992959126859730663421261680620800","05962050583197937396722560435869530016150620179698"}

    28

    8

    2

    49

    Returns: 819428172

33. {"7137865775160827057780660944","2755124462936688270311931241582483370650196526219","7240232723140868876885391088529060594783178970231","03728649985832921668688822801980307616014487430281","99837259762635193110439722513339227684135207868403","2561451412054238505994663266715580717085749025602"}

    48

    4

    9

    14

    Returns: 857921425

34. {"04871018784420426687197468499235569588622465507083","73525538013141663044719255309549515739906776260236","180385851766510787450099993808580420311453999354","56884911993377599885841780644326590729671722322398","57268042918512042231504263826819397442366176249743","05443054465660598450054883406022983810490859491809"}

    42

    4

    32

    67

    Returns: 0

35. {"17363144336781447880555394168","11940221518783539942464484354791071552060470","234040022069282546315378191507598678118204","0967525348062638747427041779113541098604812705900","74490520551741610269394126108533135250269025850688","01475322244567636136435050299104312094761184791410"}

    43

    4

    15

    56

    Returns: 856953843

36. {"13719659832117585872193183724149644028805197177986","75474272473003613234380413403859345534296296873104","07727943200833094079181485571918166579180030614819","62242351490649939939603129126688137416373487331514","34774814963433642624655718243344645129753523651742","79368345398986391339688521541983634351848564000246"}

    95

    50

    6

    932

    Returns: 499384138

37. {"31356324158495449652972794363302854648123810832886","58666084873791428334978547127029926128627805103729","03210510819041970310860646544349952791485269863080","72314569510469792033107551232152890475681235448290","13718818839594978756073960431066347215879355005841","66403856000096820750204829049747983631901516776714"}

    80

    74

    10

    1130

    Returns: 483934094

38. {"86227092809580462162944946165361050176753894109756","99893663018749893444019412659507645978349903921391","50093866255792829450979470254238640969284610905932","96068349618133664518959577736954864315473331075308","10521446040420008695076239063069979845501522813173","10994512154886121236088336860792333191992217396173"}

    60

    67

    4

    556

    Returns: 91586525

39. {"91120741594441111124207962383942903742128105488224","70625086496656839401009570158255660712964088084762","46424646806334676601678305822847456129939643113154","32141882928790137194039852288562033777135320835826","27776876795595168213014150647367188755184717513352","39080845545108759398949294678653192950419252261929"}

    53

    89

    7

    456

    Returns: 477859400

40. {"23252574367535500698252103014891386666711401963187","28908415879026314056845349122183903012776958805091","93279672652870410268654992471108801748147052701859","65450989581573211981370519740148205895524652064756","52869895812833143159816693545240908676270153254534","73168229128447858774993170563516074708154110424206"}

    76

    72

    12

    857

    Returns: 0

41. {"71809186581667894588830055169282849292096355338874","76629393715370059166572908362333904935072592203178","96526246732604431453932360739523571006618156795430","87715655933023353450361919993058541792367774538106","70625293716318395222825712622875918325843261810361","03967818611526680946842437684139032309647707920077"}

    300

    1

    2

    9

    Returns: 0

42. {"64126838061898845416715197104889581612795312552319","35296132263021313547780844388507563812172863026112","95331395334559744834633079867899050784342958605891","90513262005026335717694833092794385729750214418408","10201041626841302622601524013754840124453063573689","80635693545967344296297927216394760485217311788127"}

    250

    2

    2

    18

    Returns: 0

43. {"29430845981374678572280318085854289633020799655441","24161703873084976985380071076834463233208377822121","30318456453792531633528587173374766866815637922434","13538934158423173602689945286254009089285611108503","67430176412522200948273477481395968110463554092363","45390738757328739267264533706910751044185000750843"}

    300

    300

    1

    486

    Returns: 0

44. {"15948423922109896373414839556465342800803296681385","40169547424831964721486177794035689885652455415555","81802534920823087346042609280996068755125099208140","71344477146897029655571046563114695121027344907838","40137841220975744367875150905607235087782493297245","81742971469420706303675999082694619607733976100187"}

    200

    70

    1

    324

    Returns: 497631373

45. {"81135416445804416255291983353078955901192859986725","76786142639147543974083671756616435388674434192838","65042798399054182833092661284478456060142431242236","18517715584332295793813149149556298707808714419737","37048511526210730910561695362622773495610418575107","81324769583379046469895445709765335278531343513032"}

    200

    70

    1

    333

    Returns: 244462546

46. {"25968232117382674970698610025828146031634142545587","22870119928897345432044220857800255920962738998001","05493441938633463551651867118727847988043731388337","59744500780636017315926154246942165605518445520913","15323354490451621812858774611220786576886141001613","78070237327354311160398567844421812263883764879537"}

    113

    70

    2

    330

    Returns: 806468854

47. {"34907580420540385468308289297866021800525646562933","96130455085200247701168143838337240183303510097102","72694504340997888129932628496172145507967232980702","27875254310632138776030467885107530852353990576752","63269674344711453849819300702341797845518672696201","59463995963627296472603823009695183800872797481305"}

    131

    150

    1

    632

    Returns: 355831317

48. {"55029578209710853556443104469204161716860521659347","56651878911605710057624731682479560714375539302418","96549427332754906141287455419915653935111827597962","77135022603210601543062781494580414820263422951248","99540980318177410470702797617772402613280247597003","43008932694394363221348757961157384907014162140883"}

    100

    121

    2

    784

    Returns: 966819059

49. {"35453922934238546850002836934611694608738212689250","48128300860273271989212764064628693707270033553708","41345502865998314132901322536295711124768864697440","43864030076117436596258534356158221352366957422345","95443092864335015718222814091087848205081925661309","66548896828666917089761984694885987634449205845099"}

    100

    150

    3

    2400

    Returns: 423325558

50. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    100

    100

    1

    1000

    Returns: 762083541

51. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    300

    1

    1

    1000

    Returns: 1

52. {"99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999","99999999999999999999999999999999999999999999999999"}

    150

    1

    1

    1000

    Returns: 320220518

53. {"111111111111111111111111", "111111111111111111111111111", "11111111111111111111111" }

    12

    8

    4

    2700

    Returns: 418629948

54. {"53241845388809200299074898230783156026983794239870", "75911526673031313597574731938292733112228280844447", "40127349421676936215905664181723894461115195850962", "05920633799149806375543676720177090844211784635581", "24233937427205946897408563018884759503902116717251", "73498439492545800140134957553134994961929222585935" }

    150

    51

    1

    2000

    Returns: 259770891

55. {"62262316136144353216216641666421455165141254222613", "31412424254144422153244214564435163265411142462351", "21334243332163553554154255444414162426465635346523", "55246443243621265253134421265166151644354436626455", "52515356326562334151512211456542415243333644534344", "53321343656521233655244443353111131236555253325656" }

    100

    100

    1

    2700

    Returns: 762083541

56. {"111111111111111111111111111111", "111111111111111111111111111111", "111111111111111111111111111111", "111111111111111111111111111111", "111111111111111111111111111111" }

    300

    30

    4

    2700

    Returns: 0

57. {"96857474854185747485285858271", "96857474854185747485285858271524163", "96857474854185274174857474852858582715241636355", "968572416400000000000578156456", "9685747485418574748528585827155247171741", "41852718527185271718271" }

    17

    13

    11

    41

    Returns: 341649737

58. {"11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111" }

    300

    10

    1

    2700

    Returns: 0