Statistics

Problem Statement for "NarrowPassage2"

Problem Statement

There is a narrow passage. Inside the passage there are some wolves. You are given a int[] size that contains the sizes of those wolves, from left to right.


The passage is so narrow that some pairs of wolves cannot pass by each other. More precisely, two adjacent wolves may swap places if and only if the sum of their sizes is maxSizeSum or less. Assuming that no wolves leave the passage, what is the number of different permutations of wolves in the passage? Note that two wolves are considered different even if they have the same size.


Let X be the number of permutations of wolves that can be obtained from their initial order by swapping a pair of wolves zero or more times. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:
NarrowPassage2
Method:
count
Parameters:
int[], int
Returns:
int
Method signature:
int count(int[] size, int maxSizeSum)
(be sure your method is public)

Constraints

  • size will contain between 1 and 50 elements, inclusive.
  • Each element in size will be between 1 and 1,000,000,000, inclusive.
  • maxSizeSum will be between 1 and 1,000,000,000, inclusive.

Examples

  1. {1, 2, 3}

    3

    Returns: 2

    From {1, 2, 3}, you can swap 1 and 2 to get {2, 1, 3}. But you can't get other permutations.

  2. {1, 2, 3}

    1000

    Returns: 6

    Here you can swap any two adjacent wolves. Thus, all 3! = 6 permutations are possible.

  3. {1, 2, 3}

    4

    Returns: 3

    You can get {1, 2, 3}, {2, 1, 3} and {2, 3, 1}.

  4. {1,1,1,1,1,1,1,1,1,1,1,1,1}

    2

    Returns: 227020758

    All of these wolves are different, even though their sizes are the same. Thus, there are 13! different permutations possible.

  5. {2,4,6,1,3,5}

    8

    Returns: 60

  6. {1000000000}

    1000000000

    Returns: 1

  7. {100,101,102,103,104,1}

    150

    Returns: 6

  8. {4320,1531}

    1966

    Returns: 1

  9. {2745220,2719164}

    12363966

    Returns: 2

  10. {3367,4102,2587,3253,871,226}

    6132

    Returns: 60

  11. {97210633,116692730,31102433,66797644}

    112195224

    Returns: 2

  12. {236}

    2

    Returns: 1

  13. {84}

    202

    Returns: 1

  14. {120454793,123763353,70591094,57592961,121968167,21737760}

    61838038

    Returns: 1

  15. {3,2}

    2

    Returns: 1

  16. {15995,38906,55625}

    80369

    Returns: 3

  17. {4698932,406379,1973713,3524875,2085372}

    6552195

    Returns: 30

  18. {346,978,785,222,70,1038,326,598,161,825,180,1079,203,263,1122,954,845,697,1168,504,960,1084,1,1144,136,932,692,514,247,214,396,1268,781,681,1230,316,694,385,651,418,732,56,104,598,356,775,1127,1112}

    768

    Returns: 1728

  19. {3165,338,16,179,7152,1084,6082,1766,3813,5670,247,4244,2365}

    6200

    Returns: 288

  20. {33197763,45784291,77919632,98071197,53336814,94802407,79177586,60002219,53272926,54303922,3910423,4876291,31896790,83456765,6924347,94248884,45988319,36125148,43051949}

    120270243

    Returns: 3767472

  21. {4,1,1,3,1,1,4,2,2}

    3

    Returns: 4

  22. {904,1396,1313}

    2155

    Returns: 1

  23. {809,1274,362,357,707,1381,1466,636,1456,262,924}

    50

    Returns: 1

  24. {3}

    9

    Returns: 1

  25. {1104,942,1476,1124,790,981,996,687,256,421,1087,726,1182,25,1241,125,461,1082,378,881,94,1009,1358,796,1062,891,1173,1289,712,1201,1295,208,675,677,268,1096,92,1185,1355,1150,314,392}

    2737

    Returns: 125371090

  26. {1306831,1525500,2548811,26072,509540,2736073,1274554,90362,581730,2551426,2633182,1244274,760681,3165195,528058,574315,2429016,2749073,2274065,203706,659090,681453,598454,838163,958476,1503778,2314299,1798195,1579109,547904,1713570,1334074,1930378,2613869,1596285,988201,1367116,2920534,26158,1122767,2493531}

    2139946

    Returns: 193536

  27. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    2

    Returns: 860734560

  28. {2,2,5,5,6,6,2,3,6,1,4,2,5,4,5,2,6,5,3,1,5,5,2,4,4,2}

    9

    Returns: 519001987

  29. {12695794,23486919,23235384,48314689,4751879,30817009,50735895,29947513,10735369,55509272,35515668,7954342,40996747,13423068,16746950,4711188,57321792,8916564,33293919,48744251,25093810,15992229,9714077,53762834,15626908,55689420,11173316,50712646,56817321,23333824,28985560,9736373,39886811,14359372,50195578,14179647,6278221,16071593,42941349,364718,5426084,36325117,33528755,48947298,40531160,20981904,12210517}

    24247324

    Returns: 18

  30. {29,29,29,4,24,18,16,11,27,23,7,29,16,17,27,13,35,17,37,18,10,6,5,14,13}

    23

    Returns: 24

  31. {18244,29150,3455,29612,22462,30394,14684,28760,14212,5107,26243,21710,18942,13031,23080,17132,17086,15650,22491,1408,4702}

    40867

    Returns: 429591965

  32. {216,146,71,109,18,212,35}

    36

    Returns: 1

  33. {112634527,78019017,77851704,122784710,256307,104642755,157265148,129372057,39624953,16787779,30195597,16893819,68890930,7138467,115786332,8608148,123223791,161875603,159802929,68331507,86041638,135388295,154759624,3938753,11882073,138752407,139307168,93423215,71191600,22607689,100151947,51014966,100590399,140440337,63414680,83950220,47649589,151845283,163161813,137798932,147195378,806464,118052265,86841148,119824353,54157634,146962847,33668612}

    167818211

    Returns: 451123363

  34. {37448,8585,22282,1824,24344,18516,1494,34408}

    41190

    Returns: 224

  35. {23,5,16,9,6,11,2,6,9,24,12,5,9,16,18,8,8,12,6,12,8,16,16,9,22,8,13,2,8,23,5,17,20,7,22}

    43

    Returns: 488969617

  36. {10000362,7987485,4449430,9859068,3231513,8207336,2881269,8483038,7620462,13180946,2032239,9840810,1483811,4800752,10442483,1339103,3142664,4061811,7864738,2785429,4873538,7568552,16465626,5049362,12362444,335769,13172879,14691458,13734880,15920390,15278289,12007176,12161115,1907651,9851715,11863301}

    14689002

    Returns: 826469420

  37. {4,1,3,1,1,4,4,3,2,3}

    3

    Returns: 2

  38. {71130252,24126471,120376699,140439700,82549157,207745583,176241735,176592827,25937685,156369228,71669638,52561617,141457785,133305387,172381860,119586536,158621498,21444358,63054586,80696278,105510812,51507846,137065565,81763857,115227550,23133276,37064363,178280983,151175072,100338281}

    143998777

    Returns: 160

  39. {5,440,2323,1469,3812,2117,3137,2055,3227,1175,1637,3177,2287,2805,3365,1763,3509,3944,1008,902,3224,1425,1169,269,3342,3251}

    3847

    Returns: 6528

  40. {2712882,6643428,2210306,7281637,5639227,183738,777170,1180003,3204994,1280802,1642071,3044634,6043334,4320302,2880054,753659,208721,5851552,4705075,731464,1064288,230789,1321783,2928393,1382150,2431460,5629415,4681046,3403458,132664,2882001,3266364,2842327,3873621,5621925,240512,3894031,1381870,2755348,1758385,1593608,7461611,1957460}

    7850776

    Returns: 937798379

  41. {10174867,7604960,10479526,6794828,5797623,5178457,11497049,3131973,1515430,5897382,4144260,6358486,5412804,8966085,9499103,5674715,1261213,3260433,5922973,1601493,9267444,8166204,5636101,3342318,6860016,3500251,8248430,7270855,5137211,11354123,6965561,1725546,9920501,8721820,10670039,6741819,2303557,2125512,7912177,854211,877637}

    7738497

    Returns: 320

  42. {2,252,88,187}

    410

    Returns: 12

  43. {17,17,23,22,12,18,1,19,7,9,23,22,9,9,2,9,19,12,13,9,13,22,8,13,13,10,24,23,13,19,18,13,5,12,12,15,25,10,9,21,10,23,21,14,2,15}

    3

    Returns: 1

  44. {5252,6843,6440,38332,50602,41591,16500,35941}

    40918

    Returns: 6

  45. {24696665,8573459,51600716,16032161,42559790,1497220,11442051,50489659,28738698,36773233,31341165,41625281,18980843,47775579,25656876,27005346,9119269,32269864,22893088,36795273,31628370,43845766,12745768,31617500,35065938,29102689,9431141,42765961,37236638,54289439,13156007,10683060,8818577,14357143,36922556,14289110,52029765,1044222,52934026}

    12774132

    Returns: 1

  46. {4983042,3035954,702661,1090884,4955859,5193190,2651098,4770534,2238740,5193657,2241951,5831564,2933314,4730217,1290017,1743266,2753234,178347,2544815,3441602,5415928,4306107,1324395,66372,4610693,4034313,2684387}

    2823426

    Returns: 8

  47. {272,256,117,341,224,379,226,22,333}

    172

    Returns: 1

  48. {140,411}

    192

    Returns: 1

  49. {3111772,37371766,42096791,11338648,31221191,59722445,25496088,28498418,43503650,51604303,34464106,14635985,27335419}

    53213693

    Returns: 30

  50. {268688267,161859197,236096117,200092547,164146764,272688523,180403304,127773124,156949683,88009734,239463713,198478733,169728133,13297806,324699224,257577142,192979512,119147941,342832608,135196009,144479852,148714080,12476108,128694818,135591213,27186104,159993704,285600621,269484095,103654622,337522858,221123836,84895079,109293642,185800157,110932966,262626925,153430015,148400637,206122169,116231902,21874809,280735393,163106823,297632868,178623412,215850735,252464947,107746134}

    19299224

    Returns: 1

  51. {75133,5198,10392,74360,55993,50711,40140,91012,43838,17325,60471,78257,40165,98689,34748,41620,4348,92995,27840,4346,75223,197,101535,68804,69925,39419,11372,36159,61316}

    105043

    Returns: 996812723

  52. {69,110,12,83,92,98,153,35,32,205,177,22,98,10,187,58,151,5,19,29,85,24,27,43,25,146,161,56,26,70,5,167,52,39,92,58,120,107,119,10,186,123,196,84,177,184}

    382

    Returns: 174141272

  53. {776,552,786,124,568,90,316,623,49,702,370,642,425,667,483,696,609,758,91,811,739,736,262,542}

    1137

    Returns: 594002817

  54. {5904,8631,4904,986,4696,718,771,60,713,4905,7875,3708,9533,7040,7059,219,3259,2484,9335,9271,4779,7342,5872,3857,2287,2290,7343,2541,9727,106,1240,2654,4852,2456,4945,6130,9447,771,9481,3566,3878,5082,7680,5162}

    16243

    Returns: 449644357

  55. {5,30,2,14,24,21,1,7,30,26,20,8,6,30,19,4,17,24,29,33,16,21,9,31,21,2,13,5,2,15,33,1,15,32,33,21,28,28,4,14,8,24,31,7}

    55

    Returns: 368120557

  56. {21,12,1,6,4,6,21,4,16,18,4,8,20,15,19}

    16

    Returns: 80

  57. {390,33,205,135,572,226,551,439,328}

    1376

    Returns: 362880

  58. {3,3,5,5,1,4,5,3,5,3,5,2,2,5,2,4,4,5,3,3,4,4,5}

    8

    Returns: 346686958

  59. {21246276,265331220,248220036,272366667,121810886,274479434,116952054,252745426,82575335,4762623,91634585,152945612,332710378,195598652,250804318,235692524,187118393,71908241,153624991,160129796,18690403,54063563,168191645,207387108,15302017,132637444,173078736,109197848,55841750,54385256,90279917,319625453,66627943,129511356,214691628,331803953,285868154,123901108,318276827,141094903,58890278,30723649,141821973,30518176,236283752,290042458}

    644954530

    Returns: 405892199

  60. {1853808,1890829,8680842,12481775,7150052,1012308,7181275,2228387,5009867,10826958,1460371,13235036,7630686,11279152,4580061,7089146,11928622,3531288,632705}

    12018386

    Returns: 672

  61. {222,117,172,98,166,15,64,74,22,170,166,126,22,41,19,35,173,112,115,182,199,45,58,216}

    210

    Returns: 15628032

  62. {22,24,38,9,35}

    32

    Returns: 1

  63. {17533,23783,8100,16802,1215,18880,11907,15082,11169,18331,16906,26934,18330,29134,31654}

    14343

    Returns: 1

  64. {1,2,3,2,3,3,1,1,2,1,4,4,4,1,4,2,1,2,1,4,2,1,1,4,1,4,1}

    8

    Returns: 394134213

  65. {17252,2810,21271,5906,8496,19384,13433,12822}

    41433

    Returns: 40320

  66. {40,42,1,17,51}

    52

    Returns: 5

  67. {178659114,68668,136954623,39478362,3749783,173815773,97875240,152593123,189798209,183779393,118803580,77105364,194293656,194214174,176774894,72357707,86710342,82028990,151696447,81423887,177043893,8915094,14577784,34071430,71240814,163708468}

    239131612

    Returns: 567487447

  68. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    1

    Returns: 1

  69. {99,637,727,838,297,802,591,640,495,112,221,758,122,218,667,33,579,698,431,841,185,475,416,866,663,72}

    235

    Returns: 1

  70. {132857,263718,27136,51151,143014,214270,20982,283767,22015,220631,41883,36633,334062,40265,230303,283641,334762,45447,117635,128423,328168,67329,226037,255228,22761,106611}

    313151

    Returns: 2851200

  71. {11,14,22,23,11,9,6,21,9,6,23,20,23,8,17,16,16,21,13,14,12,5,18,22,10,22,14,13,3,5,9,1,20,9,21,11,1,2,15,20,1,10,23,11,17,3,19,3}

    14

    Returns: 360

  72. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    2

    Returns: 472639410

  73. {8564,84691,70115,44225,175921}

    4540

    Returns: 1

  74. {24879,20694,67324,5599,2670,26318,26523,46523,17556,1650,72976,55930,70151,31848,48869,75478,45706,47992,19468,9380,41109,81453,24976,53726,70684,27268}

    77646

    Returns: 2257920

  75. {32003292,17925701,32330241,27136803,15067910,28465761,30909096,6310116,7084904,15756245,21349511,12820970,25006722,1322528,31387388,3115233,21834792,34764295,26793783,9300937,34982292,3816593,25116229,13767107,11998878,2201753,3257332,14953832,27884249,6167129,27594267,3767603,921079,14346090,29731738,34287479,19748684,30779803,21802236}

    69512780

    Returns: 722492941

  76. {16251330,70653590,41682177,24472755,47653452,31913281,55046045,64907251,82922924,68239119,58096595,6359307,84686828,70370773,8926852,57129628,48471402,46613726,33678013,69955902,36285019,22490260,28018387,62117001,32881451,20173090,16381219,23507800,45826338,88231273,87711136,56345179,13174570,9278144,35408120,22820023,43211938,23157290,66099917,65158234,58514716,81015512,13555788,77746818,11034950,73563247,40842531,49872099,13537562}

    163153597

    Returns: 63128812

  77. {16820138,37690520,17457342,11344014,13893015,47533156,17370315,22851415,5349067,33173603,37140836,14575424,20376471,33323510,51273493,20947885,26140008,11287729,12012238,29670654}

    42733522

    Returns: 3840

  78. {492968599, 52987364, 213877596, 9891638, 737497476, 117201213, 572825921, 80096143, 706122628, 874934085, 677764609, 763005176, 496896709, 832679607, 556177074, 82769609, 495663870, 58279471, 966492794, 719064880, 564701156, 913632412, 735621837, 73843615, 433743312, 588606353, 472216770, 925882480, 605380221, 315675297, 476667850, 987532479, 54981315, 877687962, 963318052, 952176401, 155809228, 335851896, 956438939, 51541996, 854838505, 284230606, 890257217, 499277953, 364672951, 750461579, 216392436, 210308371, 810675641, 412266849 }

    500000000

    Returns: 24

  79. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    2

    Returns: 318608048

  80. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    5

    Returns: 318608048

  81. {3, 8, 8, 8, 8, 8, 10 }

    12

    Returns: 6

  82. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 }

    1000000

    Returns: 799434881

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: