Statistics

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Taro and Hanako are playing Rabbit Puzzle. There are three rabbits and three nests on a line. You are given a long[] rabbits, where each element is the initial position of a single rabbit, and a long[] nests, where each element is the position of a single nest.

They must perform the following routine exactly K times:

1. Choose two different rabbits A and B, located at points a and b, respectively.
2. A jumps over B and lands at point 2*b-a.

The jump is not allowed if another rabbit is already at point 2*b-a.



The jump is also not allowed if A jumps over more than one rabbit.





The goal of the puzzle is to have every rabbit be in a nest after the K routines. Note that the i-th rabbit doesn't necessarily have to be in the i-th nest. Return the number of ways to solve this puzzle, modulo 1,000,000,007. Two ways are considered different if at least one jump is different.

Definition

Class:

RabbitPuzzle

Method:

theCount

Parameters:

long[], long[], int

Returns:

int

Method signature:

int theCount(long[] rabbits, long[] nests, int K)

(be sure your method is public)

Constraints

• rabbits will contain exactly 3 elements.
• Each element of rabbits will be between -10^18 and 10^18, inclusive.
• rabbits will be sorted in strictly ascending order.
• nests will contain exactly 3 elements.
• Each element of nests will be between -10^18 and 10^18, inclusive.
• nests will be sorted in strictly ascending order.
• K will be between 1 and 100, inclusive.

Examples

1. {0, 5, 8}

   {0, 8, 11}

   1

   Returns: 1

   The only solution is moving a rabbit from 5 to 11.

2. {0, 5, 8}

   {0, 8, 11}

   3

   Returns: 5

3. {0, 5, 8}

   {0, 8, 11}

   2

   Returns: 0

   They must use exactly 2 jumps. It's impossible to solve this puzzle.

4. {5, 8, 58}

   {13, 22, 64}

   58

   Returns: 0

   This puzzle is also impossible.

5. {0, 1, 2}

   {1, 2, 3}

   100

   Returns: 0

   This puzzle is also impossible.

6. {5, 8, 58}

   {20, 26, 61}

   58

   Returns: 537851168

7. {67, 281, 2348}

   {235, 1394, 3293}

   83

   Returns: 167142023

8. {-1000000000000000000, 999999999999999998, 999999999999999999}

   {-1000000000000000000, 999999999999999999, 1000000000000000000}

   5

   Returns: 29

9. {-420196140727489674,259695496911122584,679891637638612257}

   {-2,0,1}

   100

   Returns: 950133148

10. {-783537067827134388, -49374526719065532, 684788014389003324}

    {-783537067827134388, -49374526719065532, 684788014389003324}

    68

    Returns: 375817728

11. {-293681465505333255, -251974247525304839, -210267029545276423}

    {-293681465505333255, -251974247525304839, -210267029545276423}

    98

    Returns: 237328179

12. {-917610276352463760, -254801148925963744, 408007978500536272}

    {-917610276352463760, -254801148925963744, 408007978500536272}

    50

    Returns: 186893853

13. {-311384148376454820, 200713102068447535, 712810352513349890}

    {-311384148376454820, 200713102068447535, 712810352513349890}

    2

    Returns: 2

14. {493108906868406183, 593960506982651096, 694812107096896009}

    {493108906868406183, 593960506982651096, 694812107096896009}

    26

    Returns: 85836758

15. {-8032725280632832, -8032714976061323, -8032704671489814}

    {-212698394337504574, 689465728381722454, 894131407743165705}

    93

    Returns: 204629902

16. {-387606415324613991, -387606415324613921, -387606415324613851}

    {-785142993219220211, -208276970997003771, 189259606897602519}

    96

    Returns: 1

17. {476954908052919956, 476954908058071071, 476954908063222186}

    {208493931072205436, 642458914672906891, 910919891658772526}

    63

    Returns: 1

18. {105932750347746613, 105932750996570038, 105932751645393463}

    {-988861495078028162, -214702652803484537, 880091593271113663}

    61

    Returns: 173673344

19. {-543212329403662910, -543212329386726578, -543212329369790246}

    {-863117175719954174, -769263621075762734, -449358774742535138}

    78

    Returns: 888011565

20. {-947528085593668975, -461784293195406255, 903400588019896465}

    {417656795618951185, 417656795621633745, 417656795624316305}

    94

    Returns: 348967681

21. {-493541439946245014, 82416269924146786, 842915908833628786}

    {266931801891424786, 266958198963236986, 266984596035049186}

    91

    Returns: 230094802

22. {-455841325100844820, -113153067942400792, -17333537682781639}

    {-360024791730171328, -360021794841225667, -360018797952280006}

    94

    Returns: 244015388

23. {-831672572507845931, -268704288347527067, 643363450110974225}

    {80394337037043685, 80395165950655361, 80395994864267037}

    62

    Returns: 324985621

24. {-620992852077497854, 167885198909576390, 664918495640323964}

    {-123965438720487934, -123959555346750280, -123953671973012626}

    83

    Returns: 441778494

25. {790719780813594527, 790719781708010252, 790719783771129191}

    {-137526283556863096, 27647746932760199, 955893813366336761}

    86

    Returns: 589858395

26. {96392434709466494, 445475278658922657, 991865817014593173}

    {627605458110812829, 688315517928109553, 703493032882433734}

    43

    Returns: 89784861

27. {-325978724168150430, -165110867022030802, 317492704416328082}

    {-808582295606509314, -4243009875911174, 960964133000806594}

    17

    Returns: 121856

28. {-49187190402276492, 148649252185300719, 178624470759176054}

    {-954438791333311609, -516800600154731718, 418426219350178734}

    77

    Returns: 47314482

29. {-646656846010675604, 532881278301646731, 799603923613545111}

    {-379934200733292474, -379934200641966019, -379934200607450769}

    100

    Returns: 1

30. {-905123745169081616, 246080965080695422, 983431375660091260}

    {-905123745169081616, 246080965080695422, 983431375660091260}

    8

    Returns: 543

31. {-342416395320170522, 27770168232492714, 849196559525238823}

    {-342416395320170522, 27770168232492714, 849196559525238823}

    54

    Returns: 964342281

32. {-939663997588821827, -747466445810116427, -84673030183662899}

    {-939663997588821827, -747466445810116427, -84673030183662899}

    54

    Returns: 964342281

33. {-349639796496730812, -252316444713845184, -216667044918634444}

    {-349639796496730812, -252316444713845184, -216667044918634444}

    96

    Returns: 252477655

34. {-470316271039851002, 60597618992080514, 437585614616719846}

    {-470316271039851002, 60597618992080514, 437585614616719846}

    76

    Returns: 190645915

35. {-966081391610828832, -92375530170560928, 230611586208282504}

    {-966081391610828832, -92375530170560928, 230611586208282504}

    24

    Returns: 43608330

36. {-939164379542226603, 393572989996598702, 926667937812128824}

    {-939164379542226603, 393572989996598702, 926667937812128824}

    78

    Returns: 233323064

37. {-796042399264747108, 211914647685334541, 948999516643662982}

    {-796042399264747108, 211914647685334541, 948999516643662982}

    100

    Returns: 555380499

38. {-664139096112925554, -115723467976412364, 174386463397870206}

    {-664139096112925554, -115723467976412364, 174386463397870206}

    64

    Returns: 282806367

39. {-759349031814682171, -582725138367326741, -350188499511536091}

    {-759349031814682171, -582725138367326741, -350188499511536091}

    8

    Returns: 543

40. {115804431866303855, 115804431867969275, 115804431874030715}

    {-292923425806396285, 296349626489008955, 705077484167770535}

    69

    Returns: 9245

41. {-276386447774828749, -276346473292886710, -276216088060119887}

    {-842655025928638247, -143472162317142259, 422926801069434062}

    80

    Returns: 247688478

42. {-142689927448090214, -142689926027176314, -142689924914254049}

    {-327154623236085319, 293936905977428116, 478401602878345486}

    89

    Returns: 482944996

43. {-259261094776779676, -259261024408559758, -259261002961516090}

    {-348538959722252944, -204194902260432358, -114917015867915422}

    88

    Returns: 161721778

44. {269401723663076520, 269401723690477684, 269401723701800905}

    {-180107375167090240, 95140917946835570, 544650016788325551}

    85

    Returns: 571119683

45. {-776466996896862930, -204737590666783470, 833098309940836050}

    {261368808498957930, 261368861782625070, 261368956994423730}

    54

    Returns: 930965712

46. {156789817330068323, 524544406419169170, 590994568545733465}

    {223239979341421087, 223239979718908955, 223239979834120486}

    75

    Returns: 450850843

47. {-931750980217695390, 72067458586250410, 455590624439662050}

    {-548227816903854350, -548227813650638510, -548227811111067910}

    89

    Returns: 518883543

48. {-702903889525950810, -101925340694471160, 76280812284443940}

    {-524697736554231210, -524697736544397360, -524697736537201860}

    60

    Returns: 119

49. {365764509190227748, 547776094525036740, 962188935443370500}

    {779845462117442692, 779917526743375620, 780249414734494436}

    53

    Returns: 542840931

50. {-917748911194909313, -768938565859749447, -724734520321684660}

    {-901550702473943808, -857346656935879021, -829340820118779739}

    47

    Returns: 92755307

51. {-912834846296946277, -706924989701414111, 648131518723439662}

    {442213010295665212, 442244458193913055, 442253110026155339}

    64

    Returns: 133608384

52. {142779899440637091, 189574891088003192, 262658080967342631}

    {-969603285588111521, -199441023125614182, 986025351782473869}

    98

    Returns: 1

53. {455526397341349211, 455526397361018039, 455526397395867217}

    {-29460316126479901, 232810509478766875, 717797222981445165}

    80

    Returns: 12479

54. {-157616614230554908, -157611661714447180, -157604881901067456}

    {-960444504404512892, -344416488776958768, 458418181210378940}

    44

    Returns: 102079

55. {-860627725207365364, 233181309424517038, 920911576015256870}

    {-173004076865870408, -172558668408102906, -172452050158858030}

    92

    Returns: 100266547

56. {-133874362261546729, -131608148466473404, -127255320891391354}

    {-361741972484442904, 764264197573493096, 996484635371471321}

    100

    Returns: 841661442

57. {153144437775409700, 234994936808605936, 366811335878621040}

    {-68474800556113356, 145516894842340832, 498952532243878992}

    44

    Returns: 87

58. {-516479169148433040, -516475354528297024, -516435737938358954}

    {-627764834574079286, -453576937207148384, -342251655191564068}

    76

    Returns: 11247

59. {-519860462998691312, -519860043115795704, -519859460624779311}

    {-869864365244934656, 633997038376413852, 984001523113673589}

    86

    Returns: 803927

60. {-678937303604070164, -671037595773484082, -669936591197792642}

    {-836188282127200082, -738281450233838780, -579929467135017422}

    45

    Returns: 605327998

61. {-528613396185916527, -201098264969478419, -113141613721121617}

    {-440656888083747711, -440656071818840973, -440655928672652987}

    95

    Returns: 189

62. {-620118067688270485, 263292693698369199, 897308595922092780}

    {13897831238697411, 13897832094716894, 13897835391472579}

    82

    Returns: 163

63. {-182733322300151616, 53485977840789488, 190440538256114608}

    {-173597840401326672, -126673589977489808, 1145488539010368}

    71

    Returns: 1

64. {-501281730818493614, 401161292307988324, 711753207436717148}

    {-190690693323867020, -190690140213831584, -190689262579729354}

    98

    Returns: 1

65. {667895369280299803, 667895372990421103, 667895375587506013}

    {341245615638307573, 529138197242913943, 855787953481991083}

    95

    Returns: 700146660

66. {-731054691914989813, -375257949674412643, 212119151603117208}

    {-143678008168261783, -143676575193805242, -143676157663003421}

    93

    Returns: 72858404

67. {-258648146242800394, -258648140047423212, -258648125025483316}

    {-560215310979101944, -89531632778675354, 212035546979566092}

    55

    Returns: 5829

68. {41781750650172943, 60809768409706823, 74724659363077105}

    {-429729258919549541, -111954775888508411, 373471124634584355}

    91

    Returns: 894479113

69. {510949314472736451, 527677153081292730, 599549813388538719}

    {396879537676263123, 469017297389735790, 654959734493455107}

    87

    Returns: 131520815

70. {-27830918006887363, -27830299640123751, -27829681273360139}

    {-665610687795722491, -387493433826825759, 250286954328772981}

    41

    Returns: 0

71. {-977537342492224959, 287162333786612891, 981413051913469241}

    {-283286624403198959, -283286624365368609, -283286624327538259}

    75

    Returns: 0

72. {492360303889880553, 492360303889889913, 492360303889892773}

    {-595033835187198527, -113968725077894547, 973425413999187393}

    100

    Returns: 0

73. {-336127426462995939, -336127426029505896, -336127424625270750}

    {-888661577510264085, 320556017686651980, 873090170138155272}

    74

    Returns: 0

74. {-737386015515776117, -178925073309629180, 497891099931844376}

    {-60569842274304381, -60569842274303984, -60569842274302164}

    97

    Returns: 0

75. {-779570473498647329, -595929014684652866, 216270043759539131}

    {10622548749463787, 38528155009657719, 60534191205738600}

    77

    Returns: 0

76. {-20284587640483430, 667427185897717360, 929724109050254673}

    {242012334720183620, 242012338985267550, 242012339777137813}

    67

    Returns: 0

77. {-983522648915318398, -629973818794346332, 889127400017241464}

    {524757027996123638, 603562586411361236, 614384128311506996}

    76

    Returns: 0

78. {-444287945152454832, -390810586073252382, -106650574559699808}

    {-457903450543413678, -387652875346670904, -89877358442159484}

    91

    Returns: 0

79. {0,1,2}

    {0,101,102}

    100

    Returns: 1

80. {0,1,2}

    {0,102,103}

    100

    Returns: 0

81. {-998224527644577708, -958616385797002422, 99754954770217413}

    {-904596259894723546, -303356394092570409, 14969857098461483}

    23

    Returns: 0

82. {-824171387295311631, -801124104773570860, -653148257818896500}

    {156493206411181133, 287427541619657549, 920564497162011550}

    9

    Returns: 0

83. {-379377034964804481, 715913976181767025, 962611882627452825}

    {-244760933818930193, 44166371198368943, 45788008650128259}

    42

    Returns: 0

84. {29310791855798685, 195065233088722611, 734625072129360769}

    {-335003109161443975, 329664136722459779, 772492420647225790}

    60

    Returns: 0

85. {-885650032731922525, -736151772939427213, -413771692331348216}

    {-710822925545120396, 408868303382291843, 561216254841066227}

    67

    Returns: 0

86. {-985381481609649018, -721741938139475917, 746900631426100177}

    {-317763365208358594, -170088689598251383, 630935763566034287}

    76

    Returns: 0

87. {-172887830240714141, 93681602709545759, 802212424239412689}

    {280214080066629020, 514836832300533998, 770265743523057767}

    50

    Returns: 0

88. {-728498937189378807, 415387553107654315, 781319897589279127}

    {-712310018945224796, -503536690686727040, -153793264449256239}

    66

    Returns: 0

89. {-449696031602920369, -62146032689234572, 796493162577351081}

    {378684797004236157, 590671580971071827, 620929947630500954}

    1

    Returns: 0

90. {-942126411045580847, -411637212324962713, 236820088195651702}

    {-865121317134959208, -459981345794175822, 111470860815816954}

    69

    Returns: 0

91. {-710926933494011179, -106748849659950611, 337499741394505689}

    {-439088197609765380, 94010111655582180, 484948871783503724}

    64

    Returns: 0

92. {-641271694653678009, -311552615144668071, -207877589606493561}

    {-841039615711003143, -368686359850373895, 857522262755177167}

    25

    Returns: 0

93. {-781267101334675387, 214642104506346179, 600721444215640883}

    {295025036309152707, 349865851608768432, 549486419299369671}

    69

    Returns: 0

94. {73133795479620678, 261133810338192486, 581776670845602326}

    {-355158372698439817, 370756167019337463, 396324270809415911}

    75

    Returns: 0

95. {-34409219915912530, -3464988679282546, 433231736061823374}

    {104140173909123611, 449571047360347899, 490465181261465851}

    96

    Returns: 0

96. {-97107192779722644, 295880660023357798, 390488846809284663}

    {-9776558823484752, -2499005993800743, 4778546835888230}

    15

    Returns: 389

97. {1396978889714814, 5464317432538095, 8175876461088043}

    {4108537918261480, 5464317432531531, 5464317432534813}

    50

    Returns: 948952738

98. {-726549176455284522, -311073854929375360, 411061822960895463}

    {-578165133052871117, 104401466596476402, 678153101084333820}

    68

    Returns: 643396901

99. {-731657988370371598, -160137264743262318, 568468102219953043}

    {-811871423266498440, -367355304889256666, 441463496970085537}

    98

    Returns: 369704520

100. {2350444572957550, 3230630382361316, 3230630382362827}

     {-800379013603772650, -468548963458347372, 334180494718384339}

     66

     Returns: 36781176

101. {-293100457846038183, 426097103787248784, 722853379218459436}

     {-181380448271765541, 642554622336486690, 827590888193424700}

     96

     Returns: 153947296

102. {-6530759510510383, -4973999851227080, -3417240191945275}

     {-11201038488372276, -9644278829085977, -3417240191942279}

     95

     Returns: 218418883

103. {-25840041051358801, 28949146360087806, 50864821324667178}

     {-3924366086783075, 7033471395508434, 7033471395512080}

     75

     Returns: 589447894

104. {-84210047227261550, -25046912712692293, 60121995214874414}

     {-70557016185212403, 152442490830537828, 223958367716055388}

     78

     Returns: 991056060

105. {-2278641201888414, -274468461963280, 1729704277961373}

     {-2278641201888414, -2278641201887933, -274468461963280}

     3

     Returns: 5

106. {-4257135148943815, -588721942975366, 1245484660011528}

     {-429793067043809246, 311226400566200771, 738596539064053096}

     69

     Returns: 540431845

107. {-957258367109511612, -339178391536077155, 620333865161492459}

     {-444234478031178485, -132568088085201609, 313920279534034878}

     59

     Returns: 179091395

108. {-16474783251636959, -7969512013177080, 4788394844510870}

     {-569317413752130751, 242935989521649072, 808536526879830814}

     23

     Returns: 13109

109. {-665227890202155123, -233873250989828367, 435861583576678910}

     {-824148020437580033, -506307759965606015, 322347204836326172}

     30

     Returns: 1679

110. {-226185132014872071, -187503262183261682, 34917489348499388}

     {-854765516778224912, -671026635078143560, 179974501216970351}

     71

     Returns: 187445319

111. {-669331411575285687, -239917366884790187, 431591525048535854}

     {2177480358035819, 2853722948093321, 2853722948097856}

     77

     Returns: 960561169

112. {-552103967139718659, 384784879425114853, 939521696470082036}

     {-206934392089508423, 779264393768171453, 988831635762928400}

     92

     Returns: 671041552

113. {-106348867900415878, -38910546491962962, 68327440010003225}

     {-216427651050192, 1994664854146255, 3100211106746756}

     13

     Returns: 25

114. {-517044516111949, 5877630410591444, 5877630410598475}

     {-517044516111949, 5877630410584413, 5877630410591444}

     37

     Returns: 267344849

115. {-30939879990800543, 106793661245976944, 136307991511000771}

     {-1425549725777833, 8412560362563815, 8412560362564932}

     88

     Returns: 164747078

116. {-343809844425079649, -98309140644323762, 78001697786960025}

     {-786327523251989459, -786327523251496122, -167499005993302525}

     96

     Returns: 0

117. {-831524332176950533, -831524332176801957, -786509225106315126}

     {-786509225106466577, -786509225106465546, -786509225106462671}

     45

     Returns: 0

118. {-771054703935523492, -771054703935356597, -694345030297609985}

     {-694345030300319218, -694345030290756663, -694345030288214325}

     39

     Returns: 0

119. {-388445752145317090, 248921445280698711, 248921445280701991}

     {-388445752145319067, -388445752145310151, -388445752145304894}

     75

     Returns: 0

120. {-998626708227176453, -998626708227156608, -998626708227131409}

     {-998876062595734822, -998876062593566543, -998626708224982975}

     55

     Returns: 0

121. {-565528458671219167, -565528458669620388, -565528458667675121}

     {-579666933422409083, -579666933421719312, -565528458668584129}

     28

     Returns: 0

122. {-769683953660208912, -769683953660208763, -769683953660208640}

     {-769683953660297118, -12255605529305942, -12255605529217613}

     38

     Returns: 0

123. {-392407508350520673, -392407508350362981, -392407508349982498}

     {-394083421107540518, -394083421107322885, -392407508349922557}

     57

     Returns: 0

124. {508035976505495492, 983189606011741490, 983189606016059469}

     {508035976509400988, 508035976509735298, 508035976510147781}

     17

     Returns: 0

125. {514393367619902332, 546225461016069803, 546225461016081427}

     {514393367619913951, 514393367619913959, 514393367619913964}

     6

     Returns: 0

126. {-1000000000000000000, 999999999999999999, 1000000000000000000}

     {-1000000000000000000, 999999999999999999, 1000000000000000000}

     100

     Returns: 390514867

127. {-1, 0, 1}

     {-1, 0, 1}

     100

     Returns: 19254083

128. {-50, 1, 2}

     {-50, 49, 50}

     100

     Returns: 245953932

129. {-1000000000000000000, 999999999999999999, 1000000000000000000}

     {-1000000000000000000, 999999999999999951, 999999999999999952}

     100

     Returns: 245953932

130. {-100000000000000000, 99999999999999998, 99999999999999999 }

     {-100000000007000000, 99899999999999999, 100006000000000000 }

     72

     Returns: 0

131. {-310930377, 192187238, 503117617 }

     {-268628057, 166040015, 434668074 }

     100

     Returns: 472951823