TheRealSamuel/LeetCodeProblem

1 2module Main where3import Test.HUnit4 5--Program start6 7--Program end8 9-- Test cases10 11test1 :: Test12test1 = TestCase (assertEqual "for (minCost [20,1,15] 5)," 13 (minCost [20,1,15] 5))13 14test2 :: Test15test2 = TestCase (assertEqual "for (minCost [1,2,3] 4)," 6 (minCost [1,2,3] 4))16 17test3 :: Test18test3 = TestCase (assertEqual "for (minCost [195199014, 984800196, 607924423, 36348739, 813130315, 153065099, 588296506, 617132062, 781027683, 116629882, 581208811, 569440617, 870838107, 939227748, 574241627, 488909059, 479214749, 920077184, 809104907, 97812621, 739489242, 733086437, 654080955, 987436545, 140526391, 372643245, 149983222, 229866605, 912832555, 986734995, 161610887, 660721797, 431179104, 37923818, 337467714, 344568419, 408880028, 298866142, 586368843, 655456322, 182642371, 81945619, 607613577, 887811013, 626376923, 715066277, 27312739, 242413291, 491056317, 626066721, 329827884, 51373087, 377603455, 285888257, 289189990, 437036712, 51492615, 773483380, 273050223, 239823783, 178687773, 86195843, 311103091, 513170145, 818474194, 861218557, 673632638, 973212016, 990596428, 584797315, 390187131, 16063215, 671830121, 403723544, 368926620, 291577238, 836588088, 603827758, 2606594, 259323471, 249091497, 372920588, 781724843, 390173853, 817933194, 302969239, 164540460, 652257475, 452847149, 751974372, 417340325, 609385790, 325428582, 5518899, 689255278, 306884488, 240441423, 990221737, 127779717, 469798221, 809710543, 76651043, 114721605, 811337085, 838269422, 210573940, 550804251, 151059732, 963856152, 454169768, 649700828, 863499421, 666400114, 739255458, 148479307, 810214197, 701169766, 224247585, 528904494, 677094434, 656368211, 964745763, 285343955, 354199258, 604592293, 84075276, 171162476, 198006259, 792771994, 921766273, 513057436, 442342857, 393647274, 928913521, 129759381, 926801252, 382921119, 590703484, 947689972, 645597832, 80489849, 402504867, 793560817, 304668159, 752099804, 272063343, 237287828, 311417665, 110016486, 391816426, 573541853, 412955906, 774375508, 988828191, 529616010, 365784851, 130714687, 625023361, 51870264, 3921080, 970552943, 831690784, 304632280, 163415864, 945698689, 992319209, 607764312, 916603382, 69904958, 529364651, 877540295, 742675142, 217211577, 929501124, 359606819, 792089571, 628840547, 470317204, 245666470, 538467321, 542525942, 301217535, 254924657, 494655010, 462250827, 480408495, 21908896, 994013811, 32823489, 900377181, 767397312, 536885644, 109915622, 739194012, 394242870, 281165002, 684530302, 642378737, 252917803, 289701811, 920316781, 561202250, 485794592, 985927864, 452933034, 396341427, 464970466, 650547832, 435718719, 407937592, 825524338, 342161946, 794783327, 78363130, 758859001, 339179672, 276222116, 331080978, 355655498, 529702137, 246833303, 444240535, 390433754, 383207254, 685984136, 776310837, 971712059, 291328757, 498988370, 944595442, 210158741, 474588291, 728452333, 327892670, 633123722, 280937805, 961564731, 896302261, 364818399, 791196212, 678626404, 702912193, 966940719, 697837937, 229233322, 615904816, 142873499, 239716403, 88386028, 814798561, 518353881, 498482718, 458907246, 296617630, 685054486, 159771808, 423294860, 494014169, 150924742, 12436220, 755400713, 258190124, 65531288, 454041355, 221518994, 860222475, 932970280, 531681169, 602109256, 585029274, 24112250, 832975854, 702277613, 886158293, 993671856, 745950250, 9815904, 428057692, 951726244, 182913765, 886722589, 752178138, 941397089, 754737490, 328291852, 179288814, 959223573, 523585699, 542035645, 184733133, 198371804, 304883176, 998452141, 124524129, 885584699, 481174985, 616696757, 593324918, 454968615, 52844661, 970336457, 59652415, 503863689, 763412487, 318086037, 431678900, 772961494, 379979411, 748770602, 564912364, 176131533, 33162653, 811147845, 911170860, 147574219, 147811026, 152613327, 313470576, 67773459, 635593023, 923663369, 940797858, 353228924, 894589838, 113893957, 270912429, 810499926, 343383832, 999461432, 428879623, 882203250, 137842711, 963733831, 228328390, 388609130, 444731715, 876905523, 820643216, 292901933, 300114876, 646370184, 139589078, 173813411, 641490002, 511780675, 138009273, 168326041, 455523429, 577968590, 822486887, 206628466, 406962072, 776818543, 243949136, 773326982, 943666446, 751147131, 535649421, 445290504, 493015215, 441504843, 460178556, 176659001, 966315793, 622966118, 99102348, 959671731, 489578182, 700131590, 692678432, 843997706, 84316992, 295052242, 553321387, 675541223, 343432650, 389473733, 370807758, 385237489, 945158723, 227527971, 875594740, 125454021, 423896252, 15560748, 6210546, 794287516, 458892965, 645223642, 996372617, 537229661, 954211580, 293738043, 696027865, 46737506, 80039731, 692608133, 145885645, 560041641, 318623001, 562827220, 742688194, 100673661, 178786795, 289815352, 652188537, 735242308, 734937272, 891739424, 664946181, 987635466, 788629312, 402822043, 955411387, 929766648, 410007672, 377269822, 561962151, 937239079, 13238555, 966880602, 905525735, 233868138, 123894478, 827850053, 613602240, 649224028, 208377928, 317404952, 872164249, 238027473, 603347539, 15913528, 511476986, 60472308, 825530316, 575387964, 10613894, 817509174, 745601985, 316498340, 393598793, 909624006, 14905850, 215533967, 411912051, 984884312, 749494941, 678806049, 509115086, 312513897, 436730186, 622622583, 410981845, 6187747, 240335095, 871466569, 298738342, 753964255, 842764464, 763669249, 726831257, 262805735, 456928993, 921464338, 398268879, 902183475, 491502741, 872348170, 244442294, 715060792, 925352396, 588960406, 463602725, 881739070, 317752390, 709787883, 704456597, 239353639, 42648361, 330506671, 881390592, 270400733, 431217820, 923604163, 199350714, 730784157, 618816379, 390154481, 510752733, 419362979, 7864821, 670638993, 931944085, 877025976, 356710805, 580480749, 523376265, 32536697, 534640272, 658422828, 602869101, 257627936, 19353320, 307231189, 767777638, 116075954, 910132199, 890785831, 112656238, 535125877, 899585967, 212528780, 52594748, 476910963, 702000280, 914379828, 232401095, 815622453, 170806089, 142026010, 974803062, 446266689, 647729617, 141540830, 209984756, 917469850, 366614793, 505088170, 336199776, 458282243, 776726118, 65898399, 588747470, 336803515, 227473240, 807022596, 76282996, 556822238, 890598517, 320719589, 833641979, 274922280, 850612850, 805689839, 350345518, 268524345, 537854273, 133048817, 941825930, 531193388, 234420006, 652476571, 376886332, 471886483, 966682042, 169210281, 794515277, 84541212, 702197814, 294385154, 932048350, 357165852, 106845267, 838294046, 268767026, 768928242, 317757906, 642134607, 866468112, 408162350, 316778091, 315071199, 946231322, 462597803, 803470909, 113477738, 981387113, 350882681, 622688065, 877058174, 707677845, 678125185, 987244185, 416176335, 435153468, 898770636, 739742120, 368770071, 718975205, 132449699, 112157585, 614954407, 277410771, 845349804, 41620036, 459533573, 440667505, 351711058, 51265070, 692281115, 414086736, 582255027, 278173598, 837369224, 134070537, 411382375, 783386478, 59113229, 20075845, 11128092, 578770990, 239563044, 539793169, 405961871, 465019583, 881445046, 379539062, 604898363, 846257377, 120473440, 286543229, 554792750, 360420609, 994274929, 647518644, 639628224, 958244598, 134806133, 982204738, 969696721, 438608528, 684891723, 401247476, 263136938, 690073753, 429568456, 758466696, 834591579, 765511214, 245834044, 5432691, 949868089, 189205914, 182922234, 267536500, 556288860, 275325798, 228763038, 43198009, 626958467, 589408140, 157891879, 191866252, 566237343, 489338090, 316442951, 378261638, 250879999, 678793094, 863771713, 91704092, 254836077, 169623528, 3163204, 173845140, 346893958, 776113836, 973508092, 645340992, 590430401, 951563534, 473705954, 729796359, 97394867, 103018547, 254535655, 60538203, 584520812, 986220593, 444323091, 965536113, 869419091, 5081692, 327462154, 643651844, 579512728, 908311364, 223782800, 784660433, 354251199, 223432445, 557927372, 132706843, 207201606, 244254156, 597845799, 764449087, 586516681, 815675472, 517278658, 500556000, 970376215, 989955500, 72034657, 206722688] 59772293)," 10633276482 (minCost [195199014, 984800196, 607924423, 36348739, 813130315, 153065099, 588296506, 617132062, 781027683, 116629882, 581208811, 569440617, 870838107, 939227748, 574241627, 488909059, 479214749, 920077184, 809104907, 97812621, 739489242, 733086437, 654080955, 987436545, 140526391, 372643245, 149983222, 229866605, 912832555, 986734995, 161610887, 660721797, 431179104, 37923818, 337467714, 344568419, 408880028, 298866142, 586368843, 655456322, 182642371, 81945619, 607613577, 887811013, 626376923, 715066277, 27312739, 242413291, 491056317, 626066721, 329827884, 51373087, 377603455, 285888257, 289189990, 437036712, 51492615, 773483380, 273050223, 239823783, 178687773, 86195843, 311103091, 513170145, 818474194, 861218557, 673632638, 973212016, 990596428, 584797315, 390187131, 16063215, 671830121, 403723544, 368926620, 291577238, 836588088, 603827758, 2606594, 259323471, 249091497, 372920588, 781724843, 390173853, 817933194, 302969239, 164540460, 652257475, 452847149, 751974372, 417340325, 609385790, 325428582, 5518899, 689255278, 306884488, 240441423, 990221737, 127779717, 469798221, 809710543, 76651043, 114721605, 811337085, 838269422, 210573940, 550804251, 151059732, 963856152, 454169768, 649700828, 863499421, 666400114, 739255458, 148479307, 810214197, 701169766, 224247585, 528904494, 677094434, 656368211, 964745763, 285343955, 354199258, 604592293, 84075276, 171162476, 198006259, 792771994, 921766273, 513057436, 442342857, 393647274, 928913521, 129759381, 926801252, 382921119, 590703484, 947689972, 645597832, 80489849, 402504867, 793560817, 304668159, 752099804, 272063343, 237287828, 311417665, 110016486, 391816426, 573541853, 412955906, 774375508, 988828191, 529616010, 365784851, 130714687, 625023361, 51870264, 3921080, 970552943, 831690784, 304632280, 163415864, 945698689, 992319209, 607764312, 916603382, 69904958, 529364651, 877540295, 742675142, 217211577, 929501124, 359606819, 792089571, 628840547, 470317204, 245666470, 538467321, 542525942, 301217535, 254924657, 494655010, 462250827, 480408495, 21908896, 994013811, 32823489, 900377181, 767397312, 536885644, 109915622, 739194012, 394242870, 281165002, 684530302, 642378737, 252917803, 289701811, 920316781, 561202250, 485794592, 985927864, 452933034, 396341427, 464970466, 650547832, 435718719, 407937592, 825524338, 342161946, 794783327, 78363130, 758859001, 339179672, 276222116, 331080978, 355655498, 529702137, 246833303, 444240535, 390433754, 383207254, 685984136, 776310837, 971712059, 291328757, 498988370, 944595442, 210158741, 474588291, 728452333, 327892670, 633123722, 280937805, 961564731, 896302261, 364818399, 791196212, 678626404, 702912193, 966940719, 697837937, 229233322, 615904816, 142873499, 239716403, 88386028, 814798561, 518353881, 498482718, 458907246, 296617630, 685054486, 159771808, 423294860, 494014169, 150924742, 12436220, 755400713, 258190124, 65531288, 454041355, 221518994, 860222475, 932970280, 531681169, 602109256, 585029274, 24112250, 832975854, 702277613, 886158293, 993671856, 745950250, 9815904, 428057692, 951726244, 182913765, 886722589, 752178138, 941397089, 754737490, 328291852, 179288814, 959223573, 523585699, 542035645, 184733133, 198371804, 304883176, 998452141, 124524129, 885584699, 481174985, 616696757, 593324918, 454968615, 52844661, 970336457, 59652415, 503863689, 763412487, 318086037, 431678900, 772961494, 379979411, 748770602, 564912364, 176131533, 33162653, 811147845, 911170860, 147574219, 147811026, 152613327, 313470576, 67773459, 635593023, 923663369, 940797858, 353228924, 894589838, 113893957, 270912429, 810499926, 343383832, 999461432, 428879623, 882203250, 137842711, 963733831, 228328390, 388609130, 444731715, 876905523, 820643216, 292901933, 300114876, 646370184, 139589078, 173813411, 641490002, 511780675, 138009273, 168326041, 455523429, 577968590, 822486887, 206628466, 406962072, 776818543, 243949136, 773326982, 943666446, 751147131, 535649421, 445290504, 493015215, 441504843, 460178556, 176659001, 966315793, 622966118, 99102348, 959671731, 489578182, 700131590, 692678432, 843997706, 84316992, 295052242, 553321387, 675541223, 343432650, 389473733, 370807758, 385237489, 945158723, 227527971, 875594740, 125454021, 423896252, 15560748, 6210546, 794287516, 458892965, 645223642, 996372617, 537229661, 954211580, 293738043, 696027865, 46737506, 80039731, 692608133, 145885645, 560041641, 318623001, 562827220, 742688194, 100673661, 178786795, 289815352, 652188537, 735242308, 734937272, 891739424, 664946181, 987635466, 788629312, 402822043, 955411387, 929766648, 410007672, 377269822, 561962151, 937239079, 13238555, 966880602, 905525735, 233868138, 123894478, 827850053, 613602240, 649224028, 208377928, 317404952, 872164249, 238027473, 603347539, 15913528, 511476986, 60472308, 825530316, 575387964, 10613894, 817509174, 745601985, 316498340, 393598793, 909624006, 14905850, 215533967, 411912051, 984884312, 749494941, 678806049, 509115086, 312513897, 436730186, 622622583, 410981845, 6187747, 240335095, 871466569, 298738342, 753964255, 842764464, 763669249, 726831257, 262805735, 456928993, 921464338, 398268879, 902183475, 491502741, 872348170, 244442294, 715060792, 925352396, 588960406, 463602725, 881739070, 317752390, 709787883, 704456597, 239353639, 42648361, 330506671, 881390592, 270400733, 431217820, 923604163, 199350714, 730784157, 618816379, 390154481, 510752733, 419362979, 7864821, 670638993, 931944085, 877025976, 356710805, 580480749, 523376265, 32536697, 534640272, 658422828, 602869101, 257627936, 19353320, 307231189, 767777638, 116075954, 910132199, 890785831, 112656238, 535125877, 899585967, 212528780, 52594748, 476910963, 702000280, 914379828, 232401095, 815622453, 170806089, 142026010, 974803062, 446266689, 647729617, 141540830, 209984756, 917469850, 366614793, 505088170, 336199776, 458282243, 776726118, 65898399, 588747470, 336803515, 227473240, 807022596, 76282996, 556822238, 890598517, 320719589, 833641979, 274922280, 850612850, 805689839, 350345518, 268524345, 537854273, 133048817, 941825930, 531193388, 234420006, 652476571, 376886332, 471886483, 966682042, 169210281, 794515277, 84541212, 702197814, 294385154, 932048350, 357165852, 106845267, 838294046, 268767026, 768928242, 317757906, 642134607, 866468112, 408162350, 316778091, 315071199, 946231322, 462597803, 803470909, 113477738, 981387113, 350882681, 622688065, 877058174, 707677845, 678125185, 987244185, 416176335, 435153468, 898770636, 739742120, 368770071, 718975205, 132449699, 112157585, 614954407, 277410771, 845349804, 41620036, 459533573, 440667505, 351711058, 51265070, 692281115, 414086736, 582255027, 278173598, 837369224, 134070537, 411382375, 783386478, 59113229, 20075845, 11128092, 578770990, 239563044, 539793169, 405961871, 465019583, 881445046, 379539062, 604898363, 846257377, 120473440, 286543229, 554792750, 360420609, 994274929, 647518644, 639628224, 958244598, 134806133, 982204738, 969696721, 438608528, 684891723, 401247476, 263136938, 690073753, 429568456, 758466696, 834591579, 765511214, 245834044, 5432691, 949868089, 189205914, 182922234, 267536500, 556288860, 275325798, 228763038, 43198009, 626958467, 589408140, 157891879, 191866252, 566237343, 489338090, 316442951, 378261638, 250879999, 678793094, 863771713, 91704092, 254836077, 169623528, 3163204, 173845140, 346893958, 776113836, 973508092, 645340992, 590430401, 951563534, 473705954, 729796359, 97394867, 103018547, 254535655, 60538203, 584520812, 986220593, 444323091, 965536113, 869419091, 5081692, 327462154, 643651844, 579512728, 908311364, 223782800, 784660433, 354251199, 223432445, 557927372, 132706843, 207201606, 244254156, 597845799, 764449087, 586516681, 815675472, 517278658, 500556000, 970376215, 989955500, 72034657, 206722688] 59772293))19 20test4 :: Test21test4 = TestCase (assertEqual "for (minCost [563669213, 825855133, 170715616, 848248921, 900296610, 887903420, 675871814, 486596683, 235735391, 414856374, 822396398, 44266810, 771867053, 915395390, 407577458, 526132977, 435493588, 200118428, 522821959, 508699245, 209107510, 775835633, 848773024, 737330318, 49170263, 680427509, 573882300, 47975331, 107865654, 717536143, 530193469, 815833575, 172088373, 245232698, 13843861, 505703667, 920495124, 239600583, 738826172, 885854894, 287143084, 855637308, 143274687, 483262375, 405384251, 100977809, 953509786, 841235525, 575644136, 728039828, 448530985, 15997067, 72457869, 101030668, 373958835, 405681725, 405119064, 640524495, 878589097, 853263253, 326180319, 905875964, 224218040, 191497343, 54231792, 209037869, 375754140, 733021805, 872850958, 680061098, 909589897, 283417467, 992550860, 786664967, 204480733, 694702469, 695974678, 964700834, 592869236, 401811813, 56938882, 269231172, 766091455, 884761542, 38371452, 154205087, 416251331, 891071809, 869898081, 49865978, 975945402, 890700102, 988503568, 763930157, 815989390, 971377022, 282112026, 877551177, 580863559, 786925081, 447744173, 90081861, 22716552, 610375817, 696503886, 894129516, 643629922, 361399122, 212873496, 24950850, 272084837, 225407940, 69118584, 585427257, 93199531, 759303736, 892684401, 54387311, 219211102, 734932330, 253133867, 287296779, 356393711, 521830829, 942986574, 835526734, 775641657, 793444573, 234586574, 305990543, 589957492, 840715257, 18793840, 61463393, 771904419, 174384737, 449298523, 998770680, 385905690, 556897939, 257114939, 75136071, 458396933, 568211851, 482458998, 156091396, 439827914, 296595468, 806556096, 759274512, 359380225, 11956902, 840335491, 186135643, 512506043, 431375016, 209975739, 955020417, 3503802, 400814123, 234876476, 576947222, 266791712, 608870365, 766466346, 707602090, 428120087, 958082253, 184905080, 433493060, 602373693, 607604421, 812112090, 502237719, 952452187, 987786539, 64846139, 324252439, 59882599, 902241415, 371692197, 546742761, 659820907, 578700678, 551662153, 613246026, 639899097, 117406911, 301855994, 957388774, 897991451, 582703892, 88142700, 266915022, 151060378, 985016617, 149325809, 67085982, 417947811, 510895036, 18308997, 718674228, 332240402, 17036994, 482912726, 351285736, 931679892, 132057383, 15285131, 726581011, 856968187, 152149953, 848842139, 282301851, 885802920, 190876914, 136959644, 148312259, 519113422, 38376962, 356726594, 942808169, 238367302, 976641835, 560402238, 39078265, 846300705, 862455098, 392081438, 13303271, 407489581, 516158738, 426092730, 230270579, 566857210, 671558383, 501070302, 305494756, 149996375, 604973608, 475691854, 535650477, 68341824, 564713481, 675904594, 571734504, 481381942, 499047210, 960241932, 559188621, 339907471, 414845928, 381969569, 412056007, 222429126, 759873667, 95557112, 447973200, 562821228, 719714521, 711258907, 102339783, 482924658, 586039964, 28020821, 110040334, 311022027, 940526292, 648295974, 922554876, 660908464, 757134079, 846179529, 416721229, 980355072, 843258633, 773348852, 966317083, 903796445, 761515397, 962889142, 201745268, 873174137, 212674858, 910042856, 94088310, 168163893, 869159155, 233037439, 230987328, 589828823, 826806352, 664994060, 471688622, 745134907, 103187429, 603229400, 516560254, 955406852, 194155723, 683367090, 424942924, 106958578, 354855672, 35586725, 477587633, 906879483, 747824680, 815731568, 209223077, 478948459, 443136667, 720477753, 440977862, 389579185, 409137367, 666006140, 759594819, 381334522, 126128657, 456579003, 930758953, 190764978, 273220669, 613582969, 239713242, 538056745, 805006158, 752633857, 703024704, 467664263, 53684952, 390578805, 577204112, 323682769, 786364144, 893936510, 950948160, 261353949, 507236096, 366069533, 494139795, 971364473, 39447797, 365220426, 851906154, 317619002, 557803119, 716377485, 174428191, 383384919, 549160022, 571289329, 76711012, 890877483, 712773829, 167470644, 354483046, 477986720, 618472061, 405821922, 218831336, 116007746, 567271319, 477663635, 580816817, 559175243, 606926231, 890403431, 339487787, 248300406, 687048731, 511158806, 678359920, 696800477, 587350397, 179474495, 340894123, 700777902, 845853210, 921124908, 918785967, 587770467, 630217706, 717362563, 595981553, 340289370, 427610929, 714563512, 262433294, 441327464, 401582640, 691140041, 420004646, 656741070, 230421845, 278214583, 730761322, 964957276, 358896796, 557503666, 853464006, 284632286, 459150133, 603336734, 385689302, 356957264, 335776266, 745677663, 725855548, 484327271, 313178752, 850926700, 101190892, 381544552, 337926553, 144349570, 880307824, 281718892, 403045929, 193797651, 519465702, 615842736, 424666106, 214198330, 283598578, 143950066, 16833080, 12717220, 786413914, 249071653, 912424496, 830410107, 366021503, 22560213, 91875567, 567986445, 848426556, 605599362, 54189090, 616921622, 302844160, 477888837, 902147730, 618349759, 30587427, 389475281, 862036284, 248639560, 820585713, 635906374, 449218765, 693837644, 435514535, 995952207, 826467537, 144181767, 531526221, 340055046, 549225799, 387397015, 197758328, 568382231, 639706585, 48358540, 791921427, 185327646, 295792559, 443161478, 443872978, 424874990, 923516857, 98659777, 929205398, 669133063, 287396465, 849895730, 69046697, 474835650, 847853778, 140104095, 603196275, 523573889, 47107877, 895667802, 45583203, 903207368, 922597616, 386665134, 315102966, 16407145, 384915734, 921778962, 804382200, 423945781, 220550809, 880908973, 4152442, 728298706, 749757480, 562235361, 345139267, 77185567, 345823595, 983601915, 844182963, 904106483, 789976799, 394995796, 82586936, 121974183, 967632643, 429796764, 982269365, 799074126, 311149901, 437651442, 519844447, 954891471, 24148725, 538572729, 332529359, 907714845, 215990041, 560502859, 423822439, 484209522, 802193948, 585532543, 966855721, 200591667, 305209084, 400852719, 50671693, 404032320, 836515671, 312576225, 827106112, 285294081, 174463950, 679285468, 855122537, 717877225, 464754682, 345419570, 998396795, 251008696, 742790620, 459229454, 11261094, 483876617, 419697596, 148940629, 916650484, 33264727, 664756256, 81541957, 31814968, 347554098, 417890484, 48888814, 495002841, 990763108, 91580699, 944404984, 133622568, 529489280, 598349305, 841118162, 827171820, 256554468, 94338459, 399748009, 691901866, 296185971, 352638666, 594647125, 284659950, 246324504, 861359917, 821604100, 759018272, 51574016, 982530864, 772588041, 626960703, 131355704, 384815790, 45503822, 96419317, 636778033, 470926487, 456342901, 840785056, 660147669, 563952086, 45348807, 353249931, 926870983, 881556238, 901518240, 925996126, 55810296, 34775496, 472505851, 61286877, 412891222, 179747697, 593260017, 373768607, 130175796, 36417300, 527747064, 92429350, 179745521, 471709998, 912637451, 627440640, 17569947, 252263488, 399000684, 559218361, 383375566, 562068110, 269335761, 101801587, 377797666, 751335451, 958800405, 57913847, 157753477, 921672660, 109999537, 808578430, 903864677, 484110353, 394313430, 136556627, 288535485, 958769834, 300259254, 352195823, 950518461, 180748521, 798899893, 676189982, 606037456, 313955024, 75729256, 680539579, 2269609, 519317676, 875184572, 694575379, 878790683, 979567404, 944184077, 155049229, 436317053, 321749806, 489236705, 763323080, 282028232, 743281357, 498966870, 430221940, 681965311, 926694370, 632135135, 849107909, 230079556, 410061048, 707095537, 634290942, 600545868, 269760407, 452093469, 210219975, 375030799, 76429274, 611824173, 328943400, 105374470, 590497554, 38692832, 349252667, 212616107, 97050040, 404986286, 336667660, 17726065, 1811947, 672254249, 37398438, 691024006, 676578843, 294227226, 194888207, 29543539, 190425768, 322122266, 617590658, 644977987, 93719533, 224317322, 35597134, 101594741, 722223993, 841288301, 154003983, 290603441, 261695433, 343905287, 732488771, 771405000, 12824855, 397055298, 798549264, 375310777, 3160687, 860014925, 873755466, 687485790, 108741641, 591548296, 119514663, 93335768, 494385986, 212548822, 536529513, 101582885, 751996751, 216014136, 346551331, 466701529, 438133154, 467953069, 334942634, 243440098, 457302027, 674636140, 718529249, 921612110, 779217058, 713583046, 666824893, 530074627, 9576019, 634073373, 231163140, 678924307, 997121878, 775112239, 83159589, 589772529, 212385868, 829768562, 821963365, 976623024, 324977907, 280158329, 88452334, 779077084, 671705193, 842545869, 727153452, 617856355, 911851809, 288511425, 607060512, 328007906, 637897761, 242534940, 103623504, 246256, 690448636, 660405358, 549713658, 129667412, 790180837, 57599614] 531004303)," 37685090039 (minCost [563669213, 825855133, 170715616, 848248921, 900296610, 887903420, 675871814, 486596683, 235735391, 414856374, 822396398, 44266810, 771867053, 915395390, 407577458, 526132977, 435493588, 200118428, 522821959, 508699245, 209107510, 775835633, 848773024, 737330318, 49170263, 680427509, 573882300, 47975331, 107865654, 717536143, 530193469, 815833575, 172088373, 245232698, 13843861, 505703667, 920495124, 239600583, 738826172, 885854894, 287143084, 855637308, 143274687, 483262375, 405384251, 100977809, 953509786, 841235525, 575644136, 728039828, 448530985, 15997067, 72457869, 101030668, 373958835, 405681725, 405119064, 640524495, 878589097, 853263253, 326180319, 905875964, 224218040, 191497343, 54231792, 209037869, 375754140, 733021805, 872850958, 680061098, 909589897, 283417467, 992550860, 786664967, 204480733, 694702469, 695974678, 964700834, 592869236, 401811813, 56938882, 269231172, 766091455, 884761542, 38371452, 154205087, 416251331, 891071809, 869898081, 49865978, 975945402, 890700102, 988503568, 763930157, 815989390, 971377022, 282112026, 877551177, 580863559, 786925081, 447744173, 90081861, 22716552, 610375817, 696503886, 894129516, 643629922, 361399122, 212873496, 24950850, 272084837, 225407940, 69118584, 585427257, 93199531, 759303736, 892684401, 54387311, 219211102, 734932330, 253133867, 287296779, 356393711, 521830829, 942986574, 835526734, 775641657, 793444573, 234586574, 305990543, 589957492, 840715257, 18793840, 61463393, 771904419, 174384737, 449298523, 998770680, 385905690, 556897939, 257114939, 75136071, 458396933, 568211851, 482458998, 156091396, 439827914, 296595468, 806556096, 759274512, 359380225, 11956902, 840335491, 186135643, 512506043, 431375016, 209975739, 955020417, 3503802, 400814123, 234876476, 576947222, 266791712, 608870365, 766466346, 707602090, 428120087, 958082253, 184905080, 433493060, 602373693, 607604421, 812112090, 502237719, 952452187, 987786539, 64846139, 324252439, 59882599, 902241415, 371692197, 546742761, 659820907, 578700678, 551662153, 613246026, 639899097, 117406911, 301855994, 957388774, 897991451, 582703892, 88142700, 266915022, 151060378, 985016617, 149325809, 67085982, 417947811, 510895036, 18308997, 718674228, 332240402, 17036994, 482912726, 351285736, 931679892, 132057383, 15285131, 726581011, 856968187, 152149953, 848842139, 282301851, 885802920, 190876914, 136959644, 148312259, 519113422, 38376962, 356726594, 942808169, 238367302, 976641835, 560402238, 39078265, 846300705, 862455098, 392081438, 13303271, 407489581, 516158738, 426092730, 230270579, 566857210, 671558383, 501070302, 305494756, 149996375, 604973608, 475691854, 535650477, 68341824, 564713481, 675904594, 571734504, 481381942, 499047210, 960241932, 559188621, 339907471, 414845928, 381969569, 412056007, 222429126, 759873667, 95557112, 447973200, 562821228, 719714521, 711258907, 102339783, 482924658, 586039964, 28020821, 110040334, 311022027, 940526292, 648295974, 922554876, 660908464, 757134079, 846179529, 416721229, 980355072, 843258633, 773348852, 966317083, 903796445, 761515397, 962889142, 201745268, 873174137, 212674858, 910042856, 94088310, 168163893, 869159155, 233037439, 230987328, 589828823, 826806352, 664994060, 471688622, 745134907, 103187429, 603229400, 516560254, 955406852, 194155723, 683367090, 424942924, 106958578, 354855672, 35586725, 477587633, 906879483, 747824680, 815731568, 209223077, 478948459, 443136667, 720477753, 440977862, 389579185, 409137367, 666006140, 759594819, 381334522, 126128657, 456579003, 930758953, 190764978, 273220669, 613582969, 239713242, 538056745, 805006158, 752633857, 703024704, 467664263, 53684952, 390578805, 577204112, 323682769, 786364144, 893936510, 950948160, 261353949, 507236096, 366069533, 494139795, 971364473, 39447797, 365220426, 851906154, 317619002, 557803119, 716377485, 174428191, 383384919, 549160022, 571289329, 76711012, 890877483, 712773829, 167470644, 354483046, 477986720, 618472061, 405821922, 218831336, 116007746, 567271319, 477663635, 580816817, 559175243, 606926231, 890403431, 339487787, 248300406, 687048731, 511158806, 678359920, 696800477, 587350397, 179474495, 340894123, 700777902, 845853210, 921124908, 918785967, 587770467, 630217706, 717362563, 595981553, 340289370, 427610929, 714563512, 262433294, 441327464, 401582640, 691140041, 420004646, 656741070, 230421845, 278214583, 730761322, 964957276, 358896796, 557503666, 853464006, 284632286, 459150133, 603336734, 385689302, 356957264, 335776266, 745677663, 725855548, 484327271, 313178752, 850926700, 101190892, 381544552, 337926553, 144349570, 880307824, 281718892, 403045929, 193797651, 519465702, 615842736, 424666106, 214198330, 283598578, 143950066, 16833080, 12717220, 786413914, 249071653, 912424496, 830410107, 366021503, 22560213, 91875567, 567986445, 848426556, 605599362, 54189090, 616921622, 302844160, 477888837, 902147730, 618349759, 30587427, 389475281, 862036284, 248639560, 820585713, 635906374, 449218765, 693837644, 435514535, 995952207, 826467537, 144181767, 531526221, 340055046, 549225799, 387397015, 197758328, 568382231, 639706585, 48358540, 791921427, 185327646, 295792559, 443161478, 443872978, 424874990, 923516857, 98659777, 929205398, 669133063, 287396465, 849895730, 69046697, 474835650, 847853778, 140104095, 603196275, 523573889, 47107877, 895667802, 45583203, 903207368, 922597616, 386665134, 315102966, 16407145, 384915734, 921778962, 804382200, 423945781, 220550809, 880908973, 4152442, 728298706, 749757480, 562235361, 345139267, 77185567, 345823595, 983601915, 844182963, 904106483, 789976799, 394995796, 82586936, 121974183, 967632643, 429796764, 982269365, 799074126, 311149901, 437651442, 519844447, 954891471, 24148725, 538572729, 332529359, 907714845, 215990041, 560502859, 423822439, 484209522, 802193948, 585532543, 966855721, 200591667, 305209084, 400852719, 50671693, 404032320, 836515671, 312576225, 827106112, 285294081, 174463950, 679285468, 855122537, 717877225, 464754682, 345419570, 998396795, 251008696, 742790620, 459229454, 11261094, 483876617, 419697596, 148940629, 916650484, 33264727, 664756256, 81541957, 31814968, 347554098, 417890484, 48888814, 495002841, 990763108, 91580699, 944404984, 133622568, 529489280, 598349305, 841118162, 827171820, 256554468, 94338459, 399748009, 691901866, 296185971, 352638666, 594647125, 284659950, 246324504, 861359917, 821604100, 759018272, 51574016, 982530864, 772588041, 626960703, 131355704, 384815790, 45503822, 96419317, 636778033, 470926487, 456342901, 840785056, 660147669, 563952086, 45348807, 353249931, 926870983, 881556238, 901518240, 925996126, 55810296, 34775496, 472505851, 61286877, 412891222, 179747697, 593260017, 373768607, 130175796, 36417300, 527747064, 92429350, 179745521, 471709998, 912637451, 627440640, 17569947, 252263488, 399000684, 559218361, 383375566, 562068110, 269335761, 101801587, 377797666, 751335451, 958800405, 57913847, 157753477, 921672660, 109999537, 808578430, 903864677, 484110353, 394313430, 136556627, 288535485, 958769834, 300259254, 352195823, 950518461, 180748521, 798899893, 676189982, 606037456, 313955024, 75729256, 680539579, 2269609, 519317676, 875184572, 694575379, 878790683, 979567404, 944184077, 155049229, 436317053, 321749806, 489236705, 763323080, 282028232, 743281357, 498966870, 430221940, 681965311, 926694370, 632135135, 849107909, 230079556, 410061048, 707095537, 634290942, 600545868, 269760407, 452093469, 210219975, 375030799, 76429274, 611824173, 328943400, 105374470, 590497554, 38692832, 349252667, 212616107, 97050040, 404986286, 336667660, 17726065, 1811947, 672254249, 37398438, 691024006, 676578843, 294227226, 194888207, 29543539, 190425768, 322122266, 617590658, 644977987, 93719533, 224317322, 35597134, 101594741, 722223993, 841288301, 154003983, 290603441, 261695433, 343905287, 732488771, 771405000, 12824855, 397055298, 798549264, 375310777, 3160687, 860014925, 873755466, 687485790, 108741641, 591548296, 119514663, 93335768, 494385986, 212548822, 536529513, 101582885, 751996751, 216014136, 346551331, 466701529, 438133154, 467953069, 334942634, 243440098, 457302027, 674636140, 718529249, 921612110, 779217058, 713583046, 666824893, 530074627, 9576019, 634073373, 231163140, 678924307, 997121878, 775112239, 83159589, 589772529, 212385868, 829768562, 821963365, 976623024, 324977907, 280158329, 88452334, 779077084, 671705193, 842545869, 727153452, 617856355, 911851809, 288511425, 607060512, 328007906, 637897761, 242534940, 103623504, 246256, 690448636, 660405358, 549713658, 129667412, 790180837, 57599614] 531004303))22 23test5 :: Test24test5 = TestCase (assertEqual "for (minCost [945389577, 111116927, 908783196, 50140358, 959492443, 621625254, 255471618, 856293880, 431497048, 900080555, 48615242, 323695831, 793401948, 608032497, 260323249, 285572990, 862673209, 78379502, 715463944, 37841067, 420529343, 276556515, 156938055, 173291667, 926533023, 328825349, 264424263, 752255385, 748648849, 537908816, 312660609, 359083047, 552517006, 785901828, 196167296, 638340718, 38593887, 35570012, 889452149, 16700288, 309876496, 710489470, 604364097, 492912622, 578030825, 150666894, 226441865, 90711201, 185333530, 810486129, 182405455, 977957785, 733122422, 731408912, 139960041, 682401220, 681191578, 288147530, 359241124, 460311391, 233998545, 297952008, 384311367, 675987422, 273406652, 75287910, 928290128, 911238607, 407990495, 442488131, 405884137, 947079047, 99554214, 172487863, 761521355, 102878896, 560390374, 692136718, 871641505, 88140349, 989265733, 784844735, 77851623, 532924433, 269564404, 239015610, 96460813, 833932146, 121652526, 447560438, 133295611, 743001807, 500374245, 588026399, 3819236, 625802651, 303736893, 459491326, 890973172, 174644956, 948494548, 521105607, 696773235, 620297778, 573600818, 448402914, 689951348, 884451527, 521556556, 425962194, 622297134, 69255638, 321694010, 631009365, 878790060, 280461764, 594134385, 827229758, 12614167, 210065853, 169933731, 417683964, 296424875, 442481395, 718309338, 40996448, 859871255, 956044770, 231098868, 227130473, 297031090, 165391123, 873882665, 320097267, 96680241, 603126670, 267280993, 717061802, 583684867, 770546931, 638458902, 521598847, 590697046, 156440944] 711762576)," 16912494358 (minCost [945389577, 111116927, 908783196, 50140358, 959492443, 621625254, 255471618, 856293880, 431497048, 900080555, 48615242, 323695831, 793401948, 608032497, 260323249, 285572990, 862673209, 78379502, 715463944, 37841067, 420529343, 276556515, 156938055, 173291667, 926533023, 328825349, 264424263, 752255385, 748648849, 537908816, 312660609, 359083047, 552517006, 785901828, 196167296, 638340718, 38593887, 35570012, 889452149, 16700288, 309876496, 710489470, 604364097, 492912622, 578030825, 150666894, 226441865, 90711201, 185333530, 810486129, 182405455, 977957785, 733122422, 731408912, 139960041, 682401220, 681191578, 288147530, 359241124, 460311391, 233998545, 297952008, 384311367, 675987422, 273406652, 75287910, 928290128, 911238607, 407990495, 442488131, 405884137, 947079047, 99554214, 172487863, 761521355, 102878896, 560390374, 692136718, 871641505, 88140349, 989265733, 784844735, 77851623, 532924433, 269564404, 239015610, 96460813, 833932146, 121652526, 447560438, 133295611, 743001807, 500374245, 588026399, 3819236, 625802651, 303736893, 459491326, 890973172, 174644956, 948494548, 521105607, 696773235, 620297778, 573600818, 448402914, 689951348, 884451527, 521556556, 425962194, 622297134, 69255638, 321694010, 631009365, 878790060, 280461764, 594134385, 827229758, 12614167, 210065853, 169933731, 417683964, 296424875, 442481395, 718309338, 40996448, 859871255, 956044770, 231098868, 227130473, 297031090, 165391123, 873882665, 320097267, 96680241, 603126670, 267280993, 717061802, 583684867, 770546931, 638458902, 521598847, 590697046, 156440944] 711762576))25 26test6 :: Test27test6 = TestCase (assertEqual "for (minCost [787044169, 658711407, 94074275, 518527340, 34958046, 505968638, 169866082, 558364066, 996780256, 807172519, 269776645, 99028021, 824248729, 776042943, 216887087, 637195070] 76134123)," 1582855757 (minCost [787044169, 658711407, 94074275, 518527340, 34958046, 505968638, 169866082, 558364066, 996780256, 807172519, 269776645, 99028021, 824248729, 776042943, 216887087, 637195070] 76134123))28 29test7 :: Test30test7 = TestCase (assertEqual "for (minCost [344462152, 518399184, 880998883, 58782508, 790383971, 864942378, 59627709, 567315136, 855963427, 547840897, 151786106, 589178272, 308159637, 581325866, 100244626, 283608608, 931355483, 328502929, 930244029, 511510575, 46817944, 5338318, 157404917, 815197944, 325433842, 84231679, 748075803, 828287903, 8387073, 251955639, 575094145, 607580139, 154192555, 980508200, 93058551, 290680967, 657705472, 779852865, 454998097, 123457301, 994226095, 83038978, 379519601, 34603979, 963477073, 951008106, 468889481, 735796466, 764612791, 469426754, 434955762, 908077968, 564363547, 961088234, 682873684, 8497475, 439654182, 650932583, 822607245, 432758275, 58649489, 227528566, 576808310, 504387581, 9141019, 328214886, 578952787, 395355360, 245225549, 447453961, 540696166, 698804759, 183421132, 444162781, 463583501, 215760045, 682405797, 464452971, 647603901, 729797926, 812157873, 602698965, 73213430, 241471084, 115633527, 517757700, 752877919, 21976531, 558811947, 243850752, 716695544, 873580098, 635786483, 210826307, 939935933, 598383482, 825557738, 774316246, 661754805, 227134150, 514056456, 257448674, 224162661, 21418403, 606040140, 973723153, 519156314, 231883583, 879163585, 930007110, 41100278, 883953923, 154520847, 597963810, 962106202, 700236450, 369521824, 226023028, 227323918, 826345463, 930965437, 793193291, 676334092, 618862703, 201686699, 164911651, 946358967, 260389388, 392618184, 819534507, 277812808, 786004237, 182528976, 553686390, 686545749, 676005740, 27831442, 63870888, 499080954, 754947669, 559054420, 393642239, 338923114, 314311653, 245166285, 822129996, 847529195, 508783637, 196238488, 363779432, 568657291, 520788279, 88677710, 850428026, 912347444, 45701807, 105229272, 725063713, 35840745, 724133111, 168414756, 905513219, 712188313, 173025450, 778275732, 382790428, 769256959, 593775855, 478944403, 965141935, 397605536, 40816612, 637701620, 549543044, 303433120, 215515311, 503344038, 960503392, 125927893, 769639350, 172198738, 409886942, 164086343, 113582093, 41507235, 545784551, 482214174, 467822998, 483866501, 896380206, 105958129, 706589928, 680575992, 634970221, 960229785, 620362142, 439456071, 599007767, 130298623, 832938662, 43415045, 722595762, 126902357, 90494682, 949523086, 82424995, 634896590, 726282247, 750641246, 388095389, 416810383, 994674254, 378352116, 873605161, 455838986, 860091491, 817685439, 568558790, 57511057, 161342889, 943932858, 65932576, 346817904, 235733593, 728594621, 30865080, 399700749, 453468943, 126122076, 948908980, 65180579, 604714248, 997164443, 236228594, 582895182, 45770372, 480498668, 621848783, 607314949, 10806189, 903237607, 863301456, 973198812, 245329831, 648047559, 714954589, 863828161, 979659644, 461579152, 369928711, 588770319, 843757700, 682203634, 900715296, 880849515, 545693107, 714620921, 40971249, 110073571, 770641488, 563878597, 346083622, 828750480, 856927768, 424639975, 408252541, 171924937, 802760742, 256395241, 643004100, 768390236, 991956218, 296222942, 143467579, 201999757, 896876919, 540599326, 480775018, 511058071, 937205711, 585056180, 883135618, 958680743, 281901385, 675368724, 372853006, 362078981, 528829438, 51328736, 163429997, 235123483, 190318944, 637447372, 747076884] 923775125)," 26998829529 (minCost [344462152, 518399184, 880998883, 58782508, 790383971, 864942378, 59627709, 567315136, 855963427, 547840897, 151786106, 589178272, 308159637, 581325866, 100244626, 283608608, 931355483, 328502929, 930244029, 511510575, 46817944, 5338318, 157404917, 815197944, 325433842, 84231679, 748075803, 828287903, 8387073, 251955639, 575094145, 607580139, 154192555, 980508200, 93058551, 290680967, 657705472, 779852865, 454998097, 123457301, 994226095, 83038978, 379519601, 34603979, 963477073, 951008106, 468889481, 735796466, 764612791, 469426754, 434955762, 908077968, 564363547, 961088234, 682873684, 8497475, 439654182, 650932583, 822607245, 432758275, 58649489, 227528566, 576808310, 504387581, 9141019, 328214886, 578952787, 395355360, 245225549, 447453961, 540696166, 698804759, 183421132, 444162781, 463583501, 215760045, 682405797, 464452971, 647603901, 729797926, 812157873, 602698965, 73213430, 241471084, 115633527, 517757700, 752877919, 21976531, 558811947, 243850752, 716695544, 873580098, 635786483, 210826307, 939935933, 598383482, 825557738, 774316246, 661754805, 227134150, 514056456, 257448674, 224162661, 21418403, 606040140, 973723153, 519156314, 231883583, 879163585, 930007110, 41100278, 883953923, 154520847, 597963810, 962106202, 700236450, 369521824, 226023028, 227323918, 826345463, 930965437, 793193291, 676334092, 618862703, 201686699, 164911651, 946358967, 260389388, 392618184, 819534507, 277812808, 786004237, 182528976, 553686390, 686545749, 676005740, 27831442, 63870888, 499080954, 754947669, 559054420, 393642239, 338923114, 314311653, 245166285, 822129996, 847529195, 508783637, 196238488, 363779432, 568657291, 520788279, 88677710, 850428026, 912347444, 45701807, 105229272, 725063713, 35840745, 724133111, 168414756, 905513219, 712188313, 173025450, 778275732, 382790428, 769256959, 593775855, 478944403, 965141935, 397605536, 40816612, 637701620, 549543044, 303433120, 215515311, 503344038, 960503392, 125927893, 769639350, 172198738, 409886942, 164086343, 113582093, 41507235, 545784551, 482214174, 467822998, 483866501, 896380206, 105958129, 706589928, 680575992, 634970221, 960229785, 620362142, 439456071, 599007767, 130298623, 832938662, 43415045, 722595762, 126902357, 90494682, 949523086, 82424995, 634896590, 726282247, 750641246, 388095389, 416810383, 994674254, 378352116, 873605161, 455838986, 860091491, 817685439, 568558790, 57511057, 161342889, 943932858, 65932576, 346817904, 235733593, 728594621, 30865080, 399700749, 453468943, 126122076, 948908980, 65180579, 604714248, 997164443, 236228594, 582895182, 45770372, 480498668, 621848783, 607314949, 10806189, 903237607, 863301456, 973198812, 245329831, 648047559, 714954589, 863828161, 979659644, 461579152, 369928711, 588770319, 843757700, 682203634, 900715296, 880849515, 545693107, 714620921, 40971249, 110073571, 770641488, 563878597, 346083622, 828750480, 856927768, 424639975, 408252541, 171924937, 802760742, 256395241, 643004100, 768390236, 991956218, 296222942, 143467579, 201999757, 896876919, 540599326, 480775018, 511058071, 937205711, 585056180, 883135618, 958680743, 281901385, 675368724, 372853006, 362078981, 528829438, 51328736, 163429997, 235123483, 190318944, 637447372, 747076884] 923775125))31 32test8 :: Test33test8 = TestCase (assertEqual "for (minCost [73349594, 18843730, 656162099, 684433155, 13226514, 423983113, 765687789, 430398257, 290509135, 322348965, 704207495, 34083908, 444200690, 638623723, 123907037, 382686429, 965558186, 342527130, 335924564, 65126042, 236371836, 222790206, 769928664, 119302029, 202127738, 435994086, 923453752, 528400152, 424391130, 235187596, 600339609, 753668297, 839119919, 751070429, 960075585, 7443942, 315154950, 621732343, 761189424, 184642820, 6940890, 911063475, 622641120, 85837377, 647396778, 141505681, 155372287, 730012489, 19728620, 531023860, 497632163, 894995511, 493986159, 481463655, 464892392, 239820032, 703563390, 722067825, 951236797, 336243873, 735655408, 465794264, 984129082, 625906202, 636956521, 914338016, 574701587, 671935566, 318342651, 94987502, 202931506, 516517643, 741936417, 57957476, 452167236, 578276004, 984604893, 16441776, 630976802, 51106781, 10550039, 669962123, 163713000, 773850469, 174025572, 19518653, 803145634, 456041045, 665634843, 522308886, 13632988, 154974854, 408444011, 911628704, 815814669, 77224893, 201349904, 880612586, 270004008, 106408714, 384828990, 507309355, 719140605, 821135403, 191687935, 701390846, 28685387, 630615649, 537644452, 751047535, 154938223, 331543854, 197067061, 940909520, 355795924, 14509145, 651762200, 587458258, 484319565, 917779060, 415827282, 513921628, 914906031, 166196268, 842168971, 998767397, 7573687, 610972943, 443117447, 722028433, 265517549, 573760125, 999309255, 255415904, 194384066, 893465569, 183403744, 696356290, 952114946, 608950454, 502596164, 397727286, 954670358, 625244598, 702843032, 314343541, 437085433, 386707815, 565335822, 710263874, 646685777, 872220555, 672937088, 707892514, 383335678, 236236390, 190265080, 70402226, 366573021, 562865179, 261285052, 3700697, 872631939, 198644504, 291792136, 538177704, 640419422, 707052052, 837799811, 815449212, 630614876, 887573826, 897050840, 362042929, 217897115, 394668900, 784700760, 643836345, 181168174, 804953487, 647075184, 165049474, 32815617, 543536977, 212929493, 50279732, 623608418, 239073892, 144937972, 563184730, 240238830, 775112043, 315162273, 117661248, 483406074, 703243135, 679067137, 387049486, 651492619, 354753372, 575529134, 90845560, 155269823, 22092039, 862123307, 839206152, 88616784, 167034756, 97526490, 849611811, 198993990, 251914398, 384588694, 905944714, 883034767, 784758384, 973611862, 624994894, 53369112, 853961830, 189454111, 271256998, 600621789, 531461318, 455681286, 520992070, 295625425, 384414422, 420115385, 296758306, 594698057, 138773267, 123286126, 854994720, 178519394, 640778402, 404595870, 614558314, 856935997, 960452945, 967627809, 388397496, 376852547, 493499683, 111783177, 672310267, 647841265, 150107407, 4495301, 705908698, 928143684, 32973296, 775142042, 408153744, 409554005, 243021330, 426843036, 482493139, 996562109, 42338808, 744645558, 673456108, 378467098, 70425411, 436583117, 933504242, 649105661, 46890228, 849154185, 211088391, 265724624, 924861275, 927416441, 320356788, 118361154, 221637134, 809648667, 168490818, 376611335, 258007826, 956777719, 494859764, 643298863, 809609644, 883143605, 296259859, 529825461, 132611244, 485211769, 72473640, 303172197, 454007012, 845518819, 104931448, 318878344, 383003839, 347917497, 932306982, 978390636, 592335878, 722712031, 526240979, 731352897, 980715070, 254951708, 829051841, 729086263, 450990429, 110465367, 501062798, 406925918, 534144256, 557255755, 96280574, 93145647, 657967282, 71730074, 333603029, 524777672, 636573501, 120897119, 605136947, 7377400, 985615489, 739243993, 26537612, 302341787, 908823001, 761317801, 451723953, 869586374, 226229063, 579168227, 269828521, 586368858, 496389431, 556338345, 14756943, 354283251, 637955569, 990906843, 836736825, 175354731, 503885388, 244336323, 672802997, 416820981, 936718213, 255797520, 133449123, 645010808, 49835670, 909164966, 422777047, 184975250, 312411268, 723050455, 546280479, 276902296, 161098314, 775967898, 24348724, 672173236, 614667415, 749864218, 291502550, 258298788, 17262379, 449988340, 927371862, 890798513, 607960434, 936461075, 799552118, 630600884, 200839570, 182107734, 604048147, 670931799, 480546175, 506087151, 139410620, 829107848, 532317558, 354990881, 76968365, 140452440, 182527920, 233832630, 343975090, 424646397, 646544034, 637284632, 570979591, 783688356, 661354722, 627948934, 267455362, 677248686, 86661979, 742295338, 861265849, 115214081, 188361835, 342823825, 616312559, 548653470, 324605972, 674829250, 440195763, 874502545, 570058500, 699449831, 28108906, 54977773, 853008032, 607484810, 3221800, 173352506, 410061895, 989622480, 369017478, 246336327, 773272471, 842869218, 949507509, 972025944, 71209074, 68314616, 338213857, 991161332, 948876355, 31966703, 428909990, 851756807, 774303958, 782080314, 333723847, 863069047, 605737832, 644392736, 779469280, 542434779, 440255903, 538968929, 795033940, 950816010, 661986297, 367698122, 459297080, 801275661, 281662342, 447720137, 776593612, 896748278, 358596579, 432030875, 679262946, 676719267, 48500356, 499805070, 908012839, 283255214, 234570167, 351017562, 615060968, 871533898, 815124175, 146977924, 629942640, 409316288, 569895198, 272313379, 624750713, 295888774, 380179233, 620145975, 342605675, 196803090, 902674568, 627986540, 784793585, 681393196, 423105551, 467646957, 905402213, 940533796, 421660018, 764459173, 113627796, 96605240, 370072833, 624831289, 936206722, 796985376, 903024204, 678640983, 375613088, 858967151, 77859555, 672848621, 169844863, 391182217, 835055732, 154983357, 145374404, 165291938, 991376810, 580313916, 54018078, 773609970, 181741592, 389040103, 846012116, 45604765, 537558344, 264122183, 38893507, 386085740, 223059408, 856985578, 516461823, 753092701, 735302582, 732634831, 422281959, 423584239, 219528395, 796163137, 800471322, 113305943, 603235381, 612651224, 637441236, 232603244, 123505898, 506656131, 395403933, 427109971, 784114229, 780405280, 173156464, 49085757, 415133643, 834774864, 493630071, 669480906, 249310740, 919428187, 941742614, 906521552, 698087954, 857308532, 313804315, 557037327, 775171539, 983462619, 940334019, 852591, 776107103, 517637924, 242339225, 467473999, 40899203, 648483641, 175149372, 390700334, 859635637, 822439571, 296097567, 914589363, 825216059, 951898853, 273631024] 242057952)," 20226095086 (minCost [73349594, 18843730, 656162099, 684433155, 13226514, 423983113, 765687789, 430398257, 290509135, 322348965, 704207495, 34083908, 444200690, 638623723, 123907037, 382686429, 965558186, 342527130, 335924564, 65126042, 236371836, 222790206, 769928664, 119302029, 202127738, 435994086, 923453752, 528400152, 424391130, 235187596, 600339609, 753668297, 839119919, 751070429, 960075585, 7443942, 315154950, 621732343, 761189424, 184642820, 6940890, 911063475, 622641120, 85837377, 647396778, 141505681, 155372287, 730012489, 19728620, 531023860, 497632163, 894995511, 493986159, 481463655, 464892392, 239820032, 703563390, 722067825, 951236797, 336243873, 735655408, 465794264, 984129082, 625906202, 636956521, 914338016, 574701587, 671935566, 318342651, 94987502, 202931506, 516517643, 741936417, 57957476, 452167236, 578276004, 984604893, 16441776, 630976802, 51106781, 10550039, 669962123, 163713000, 773850469, 174025572, 19518653, 803145634, 456041045, 665634843, 522308886, 13632988, 154974854, 408444011, 911628704, 815814669, 77224893, 201349904, 880612586, 270004008, 106408714, 384828990, 507309355, 719140605, 821135403, 191687935, 701390846, 28685387, 630615649, 537644452, 751047535, 154938223, 331543854, 197067061, 940909520, 355795924, 14509145, 651762200, 587458258, 484319565, 917779060, 415827282, 513921628, 914906031, 166196268, 842168971, 998767397, 7573687, 610972943, 443117447, 722028433, 265517549, 573760125, 999309255, 255415904, 194384066, 893465569, 183403744, 696356290, 952114946, 608950454, 502596164, 397727286, 954670358, 625244598, 702843032, 314343541, 437085433, 386707815, 565335822, 710263874, 646685777, 872220555, 672937088, 707892514, 383335678, 236236390, 190265080, 70402226, 366573021, 562865179, 261285052, 3700697, 872631939, 198644504, 291792136, 538177704, 640419422, 707052052, 837799811, 815449212, 630614876, 887573826, 897050840, 362042929, 217897115, 394668900, 784700760, 643836345, 181168174, 804953487, 647075184, 165049474, 32815617, 543536977, 212929493, 50279732, 623608418, 239073892, 144937972, 563184730, 240238830, 775112043, 315162273, 117661248, 483406074, 703243135, 679067137, 387049486, 651492619, 354753372, 575529134, 90845560, 155269823, 22092039, 862123307, 839206152, 88616784, 167034756, 97526490, 849611811, 198993990, 251914398, 384588694, 905944714, 883034767, 784758384, 973611862, 624994894, 53369112, 853961830, 189454111, 271256998, 600621789, 531461318, 455681286, 520992070, 295625425, 384414422, 420115385, 296758306, 594698057, 138773267, 123286126, 854994720, 178519394, 640778402, 404595870, 614558314, 856935997, 960452945, 967627809, 388397496, 376852547, 493499683, 111783177, 672310267, 647841265, 150107407, 4495301, 705908698, 928143684, 32973296, 775142042, 408153744, 409554005, 243021330, 426843036, 482493139, 996562109, 42338808, 744645558, 673456108, 378467098, 70425411, 436583117, 933504242, 649105661, 46890228, 849154185, 211088391, 265724624, 924861275, 927416441, 320356788, 118361154, 221637134, 809648667, 168490818, 376611335, 258007826, 956777719, 494859764, 643298863, 809609644, 883143605, 296259859, 529825461, 132611244, 485211769, 72473640, 303172197, 454007012, 845518819, 104931448, 318878344, 383003839, 347917497, 932306982, 978390636, 592335878, 722712031, 526240979, 731352897, 980715070, 254951708, 829051841, 729086263, 450990429, 110465367, 501062798, 406925918, 534144256, 557255755, 96280574, 93145647, 657967282, 71730074, 333603029, 524777672, 636573501, 120897119, 605136947, 7377400, 985615489, 739243993, 26537612, 302341787, 908823001, 761317801, 451723953, 869586374, 226229063, 579168227, 269828521, 586368858, 496389431, 556338345, 14756943, 354283251, 637955569, 990906843, 836736825, 175354731, 503885388, 244336323, 672802997, 416820981, 936718213, 255797520, 133449123, 645010808, 49835670, 909164966, 422777047, 184975250, 312411268, 723050455, 546280479, 276902296, 161098314, 775967898, 24348724, 672173236, 614667415, 749864218, 291502550, 258298788, 17262379, 449988340, 927371862, 890798513, 607960434, 936461075, 799552118, 630600884, 200839570, 182107734, 604048147, 670931799, 480546175, 506087151, 139410620, 829107848, 532317558, 354990881, 76968365, 140452440, 182527920, 233832630, 343975090, 424646397, 646544034, 637284632, 570979591, 783688356, 661354722, 627948934, 267455362, 677248686, 86661979, 742295338, 861265849, 115214081, 188361835, 342823825, 616312559, 548653470, 324605972, 674829250, 440195763, 874502545, 570058500, 699449831, 28108906, 54977773, 853008032, 607484810, 3221800, 173352506, 410061895, 989622480, 369017478, 246336327, 773272471, 842869218, 949507509, 972025944, 71209074, 68314616, 338213857, 991161332, 948876355, 31966703, 428909990, 851756807, 774303958, 782080314, 333723847, 863069047, 605737832, 644392736, 779469280, 542434779, 440255903, 538968929, 795033940, 950816010, 661986297, 367698122, 459297080, 801275661, 281662342, 447720137, 776593612, 896748278, 358596579, 432030875, 679262946, 676719267, 48500356, 499805070, 908012839, 283255214, 234570167, 351017562, 615060968, 871533898, 815124175, 146977924, 629942640, 409316288, 569895198, 272313379, 624750713, 295888774, 380179233, 620145975, 342605675, 196803090, 902674568, 627986540, 784793585, 681393196, 423105551, 467646957, 905402213, 940533796, 421660018, 764459173, 113627796, 96605240, 370072833, 624831289, 936206722, 796985376, 903024204, 678640983, 375613088, 858967151, 77859555, 672848621, 169844863, 391182217, 835055732, 154983357, 145374404, 165291938, 991376810, 580313916, 54018078, 773609970, 181741592, 389040103, 846012116, 45604765, 537558344, 264122183, 38893507, 386085740, 223059408, 856985578, 516461823, 753092701, 735302582, 732634831, 422281959, 423584239, 219528395, 796163137, 800471322, 113305943, 603235381, 612651224, 637441236, 232603244, 123505898, 506656131, 395403933, 427109971, 784114229, 780405280, 173156464, 49085757, 415133643, 834774864, 493630071, 669480906, 249310740, 919428187, 941742614, 906521552, 698087954, 857308532, 313804315, 557037327, 775171539, 983462619, 940334019, 852591, 776107103, 517637924, 242339225, 467473999, 40899203, 648483641, 175149372, 390700334, 859635637, 822439571, 296097567, 914589363, 825216059, 951898853, 273631024] 242057952))34 35test9 :: Test36test9 = TestCase (assertEqual "for (minCost [425254684, 789699586, 176719709, 591540453, 677519448, 616408960, 419232769, 23023996, 335980679, 344379396, 678299390, 263176889, 94432418, 240120911, 159472211, 938490883, 839999189, 4546566, 67516685, 511857371, 148666704, 655902630, 785808493, 859139571, 28047068, 797282432, 991186450, 695919791, 182168185, 527562205, 691850494, 384384258, 39169180, 813590919, 814732776, 759889358, 3035120, 102478272, 770187137, 140334385, 896055107, 707568156, 497675460, 357679116, 850690716, 573027688, 16533059, 351210689, 117787744, 182515717, 559001924, 554601274, 911889785, 70201541, 697573069, 135554601, 912690408, 128329873, 361174463, 230256453, 574178412, 467147258, 4856529, 135166876, 604677104, 511652464, 907273319, 297487312, 819200135, 281037328, 377127950, 63398184, 623461021, 106894227, 502861730, 226782101, 675316836, 453350447, 544994049, 773834624, 481798977, 300205006, 233766131, 912613057, 112644316, 164606959, 468495271, 566816331, 91982538, 715343397, 720522899, 471213495, 224887693, 404226009, 113178174, 203243240, 4269437, 630673049, 89426618, 565527200, 368913199, 267084861, 863912404, 462543786, 12372219, 5438409, 378502188, 660576138, 913732767, 85750613, 888265816, 559182003, 910568422, 28860277, 948653182, 822536317, 201946566, 652437976, 808952704, 494798358, 965001211, 322193897, 654657859, 958530365, 482857021, 646926613, 428943857, 663145331, 214875780, 320149268, 491565929, 223652882, 965967912, 797841028, 930365706, 557185354, 797477294, 67710036, 413032144, 264776605, 235407699, 434335266, 732994983, 96446728, 455721547, 514527609, 950127861, 724688686, 918652338, 307023695, 518990699, 773622737, 933704889, 996275150, 513288590, 727191531, 398789874, 710672536, 316433984, 202737333, 644849163, 676102643, 293708169, 655237012, 166865611, 820098044, 664066712, 789760179, 342957626, 514949020, 269455206, 211555235, 541913607, 110928789, 792085550, 734577571, 427436652, 753654844, 194452851, 505545602, 352202349, 327112155, 561250025, 768276031, 636342581, 758985283, 390985568, 263570962, 194375367, 395440200, 495840427, 58774402, 98218434, 426326706, 508172289, 153870038, 306105453, 847398190, 327447886, 78364594, 332997036, 883837624, 780351821, 798242039, 931220599, 251576138, 593257224, 838790815, 52902269, 503421841, 523967558, 813212807, 747409226, 574002128, 432487337, 235365263, 31103775, 895260314, 453465220, 180199053, 859932439, 364960946, 85070788, 617167468, 389486148, 445918510, 680415189, 818057981, 232439179, 474617272, 590255109, 142599749, 64118808, 501542620, 670494388, 716365631, 985540348, 719256170, 905126716, 711577324, 191090139, 741298133, 170161685, 176972818, 177189726, 932226259, 631528724, 52089355, 486017688, 740460553, 997735237, 760123498, 553932613, 117747134, 161938075, 74399538, 960947525, 59269061, 633412512, 972348172, 167509535, 312357740, 568480786, 209674666, 652764959, 479611869, 789666363, 221193008, 647337833, 175735089, 271748430, 955155222, 340369678, 561837903, 936456519, 69196640, 330737103, 765929344, 653780800, 268635731, 647452265, 862903616, 337490707, 682267666, 937869467, 193371976, 158297483, 512602206, 890702600, 501716782, 980795913, 235499200, 310692588, 854514569, 512199021, 876598929, 609346426, 795761691, 215361076, 867754311, 293637541, 101127129, 878403716, 932412582, 520160573, 896453637, 986067302, 890246247, 987127082, 891485096, 41910843, 841030374, 306347047, 731922429, 834480153, 388005387, 267583246, 446779090, 847363676, 197066135, 768542647, 304404255, 765609402, 604365586, 90280380, 33947293, 295572588, 927772712, 575031317, 841815358, 669801948, 895931334, 666251251, 447271358, 339150153, 439809087, 636966421, 95073189, 120094864, 724216358, 648466512, 986214841, 595756994, 764585991, 797784250, 474708845, 489984034, 950834912, 280187025, 334690121, 311728535, 898742882, 827078115, 243072688, 160602464, 89648214, 757439879, 100451964, 694253263, 632124432, 459858292, 788649791, 293541649, 563865342, 923252753, 634484805, 322121510, 93809928, 345839538, 662243652, 456525176, 623974163, 785269305, 883270483, 76633116, 722777797, 527318058, 861039004, 680285242, 788678069, 203894403, 396236442, 372152348, 298957776, 573257661, 781041646, 518381883, 579993382, 44808192, 45109649, 493383209, 495025827, 892958739, 740817392, 951458279, 815011652, 330123825, 179500137, 139072840, 562610724, 218756925, 35859717, 393250151, 400482915, 334959185, 258768509, 667717124, 951484453, 334834725, 741240644, 899249177, 327641080, 601496982, 388984457, 105618491, 340997278, 423756896, 267133162, 856431025, 907599362, 746571907, 481426513, 548514573, 173662619, 468385700, 19040270, 351548924, 994224480, 232805696, 727821318, 877223237, 792869903, 921258903, 706694601, 610447468, 224967562, 414877357, 747172222, 222822165, 661604802, 565788675, 204464935, 991018823, 663320318, 914249489, 274261090, 558532339, 988264704, 899150808, 273016201, 883776958, 929684339, 750331359, 387490482, 471376870, 4053263, 788329502, 944166978, 507839185, 82845531, 432931248, 930749176, 871084887, 317753262, 596219785, 252234046, 570869638, 477302307, 532492662, 300727276, 43884252, 42304032, 408076532, 273926677, 483758410, 20198442, 858005202, 880633274, 966933985, 586522266, 319203090, 221985826, 824306772, 974977024, 788528887, 472311030, 365740922, 383050445, 633346853, 861784603, 518183650, 817473830, 176401317, 366278232, 564913272, 686170203, 675190887, 337693240, 143185043, 778292312, 679519713, 921758497, 576385503, 580218368, 542333146, 329396899, 695513889, 909191076, 526984661, 976129039, 154175602, 905568777, 764017252, 510986855, 523706197, 700014178, 118039873, 795143461, 610107704, 721914976, 118570932, 117794381, 704610359, 889180603, 124792373, 359394026, 809447775, 785449026, 844132069, 339380796, 867992771, 411744195, 393904595, 194894207, 874153231, 185524799, 878957794, 913051145, 532607726, 379002718, 439219160, 931097818, 559998096, 136201558, 372537584, 138104349, 138964900, 563850467, 449537477, 796958697, 158059824, 407934489, 174240304, 933645503, 94807416, 618651469, 258850185, 756310129, 418751161, 551198232, 895387254, 665580405, 12182957, 764178494, 434565709, 550431683, 560104936, 304856602, 658879860, 754218462, 520641117, 839060875, 867092916, 448586770, 725567540, 457885159, 862153220, 320392649, 608161970, 717286295, 889436722, 707629508, 887288338, 640124949, 246461851, 447247431, 61944920, 458072743, 22059319, 760585101, 812992620, 94208476, 179234940, 154388424, 746816071, 868196869, 101689701, 104237654, 169539607, 449668579, 243755662, 1538021, 811676805, 453334006, 205183057, 274742668, 667838343, 111946884, 962125160, 169152381, 164757107, 820778605, 40608265, 833933113, 597760325, 733832682, 34725313, 750514380, 648265931, 39369503, 423306694, 716955111, 599282441, 843946040, 590277616, 978431349, 468703128, 319783020, 968032855, 121112679, 322647094, 532683175, 785682928, 563305425, 807831834, 993492168, 280461808, 110696119, 18897288, 439523902, 568699607, 133201213, 670941319, 84754153, 482824980, 595587070, 177164200, 296358001, 604354785, 82842106, 433923044, 915933477, 448880627, 60737025, 418176514, 362936073, 563805258, 68570912, 404353998, 186126991, 823995182, 172728738, 374855658, 774614148, 120429944, 126745046, 931336076, 820478542, 980493003, 113784768, 717055260, 72269742, 42644502, 361627105, 567929817, 703348957, 946532162, 730642775, 896565553, 245687784, 678886682, 796306620, 618830891, 70806116, 880226499, 743923745, 402031437, 585925331, 546959035, 694849664, 450106285, 498504148, 164995692, 97797831, 201780478, 101383412, 837310657, 452459656, 80216301, 958261341, 757410412, 388221532, 299764838, 191388302, 107825463, 933699557, 946349222, 189743058, 905413045, 618057814, 595168624, 523627016, 701547170, 742272892, 523647710, 893526925, 974602185, 597983769, 752832519, 199225694, 398649835, 390751544, 126116328, 133778449, 844667619, 483019918, 921255724, 963507932, 531012367, 107268093, 619054525, 669392857, 754911136, 749025261, 84945136, 581497114, 82766065, 207819127, 638553163, 92480875, 384365757, 323053687, 5335950, 908997439, 398885318, 542185510, 508718168, 73800825, 936205007, 413642617, 440819321, 216651241, 579426546, 168774394, 637442179, 952984013, 526897232, 719833277, 592277078, 919016023, 589278432, 48295221, 928897773, 117537829, 220773587, 761919328, 37246179, 481792597, 518672953, 560915046, 22325812, 496384293, 129782091, 333684424, 277361475, 413749111, 307133884, 17027839, 948783130, 90125010, 23914083, 686549723, 758164487, 904698606, 276543444, 507287692, 774063218, 523462132, 996476226, 727343657, 632688181, 982638228, 945078904, 694865378, 512178539, 65038175, 166185516, 973025316, 31273959, 719119487, 709316127, 988643972, 659087929, 442618137, 694169527, 144824914, 355679957, 954492231, 42099116, 664835628, 784690056, 824238517, 609449964, 282716011, 878462139, 751283952, 603802723, 984556230, 402594395, 767982778, 204132253, 817564239, 841983787, 708680912, 507695129, 193801617, 315453446, 27054988, 435496777, 288750174, 452232102, 262241270, 781900442, 701528289, 210605476, 809292716, 244573828, 143639996, 796164060, 268977976, 928924013, 143457554, 337780952, 697284710, 629748888, 488316226, 821506584, 972262198, 449040254, 555479004, 684372077, 370007796, 895106216, 576169014, 432416051, 693259707, 904504326, 373788784, 187447211, 576781174, 42031404, 212913198, 323940113, 545675325, 66740570, 768153458, 177686137, 76583477, 433055702, 306097592, 351369454, 26100261, 338661445, 552403268, 444444517, 361464398, 745902080, 368071382, 501669490, 881056461, 633986960, 92376521, 447312538, 322056866, 952126970, 132907180, 779437822, 82777802, 399448521, 884216749, 755285575, 294926371, 583851237, 576562945, 363823158, 450600075, 424313903, 786756845, 317550027, 247481030, 676669472, 739666372, 222690360, 374740931, 135111876, 831106891, 173398375, 577965686, 270699985, 58752635, 177661348, 285790708, 594167835, 460062379, 573540212, 749436637, 67410690, 317300888, 271813820, 576195472, 605875333, 712345746, 648327215, 43543676, 36471202, 521878399, 852729858, 17090846, 599089449, 442278455, 32560312, 613125160, 297078716, 860258691, 811901814, 360235499, 621345610, 432328080, 940026951, 730048267, 330424156, 17400432, 844934671, 14136916, 717972741, 55003792, 820767376, 221871409, 622212918, 528119283, 82241353, 61944471, 527338055, 463757456, 95879940, 952855769, 210255149, 443105133, 83188365, 785569758, 243451089, 99791535, 946058739, 28283302, 232002549, 484217223, 351357885, 399213220, 967524989, 671336735, 293833515, 344303480, 125877988, 538086241, 472786797, 821425810, 319486050, 263760956, 237070956, 981210255, 295774140, 34348328, 439119445, 334466056, 144458817, 954458062, 131551735, 564453968] 259451167)," 38202065813 (minCost [425254684, 789699586, 176719709, 591540453, 677519448, 616408960, 419232769, 23023996, 335980679, 344379396, 678299390, 263176889, 94432418, 240120911, 159472211, 938490883, 839999189, 4546566, 67516685, 511857371, 148666704, 655902630, 785808493, 859139571, 28047068, 797282432, 991186450, 695919791, 182168185, 527562205, 691850494, 384384258, 39169180, 813590919, 814732776, 759889358, 3035120, 102478272, 770187137, 140334385, 896055107, 707568156, 497675460, 357679116, 850690716, 573027688, 16533059, 351210689, 117787744, 182515717, 559001924, 554601274, 911889785, 70201541, 697573069, 135554601, 912690408, 128329873, 361174463, 230256453, 574178412, 467147258, 4856529, 135166876, 604677104, 511652464, 907273319, 297487312, 819200135, 281037328, 377127950, 63398184, 623461021, 106894227, 502861730, 226782101, 675316836, 453350447, 544994049, 773834624, 481798977, 300205006, 233766131, 912613057, 112644316, 164606959, 468495271, 566816331, 91982538, 715343397, 720522899, 471213495, 224887693, 404226009, 113178174, 203243240, 4269437, 630673049, 89426618, 565527200, 368913199, 267084861, 863912404, 462543786, 12372219, 5438409, 378502188, 660576138, 913732767, 85750613, 888265816, 559182003, 910568422, 28860277, 948653182, 822536317, 201946566, 652437976, 808952704, 494798358, 965001211, 322193897, 654657859, 958530365, 482857021, 646926613, 428943857, 663145331, 214875780, 320149268, 491565929, 223652882, 965967912, 797841028, 930365706, 557185354, 797477294, 67710036, 413032144, 264776605, 235407699, 434335266, 732994983, 96446728, 455721547, 514527609, 950127861, 724688686, 918652338, 307023695, 518990699, 773622737, 933704889, 996275150, 513288590, 727191531, 398789874, 710672536, 316433984, 202737333, 644849163, 676102643, 293708169, 655237012, 166865611, 820098044, 664066712, 789760179, 342957626, 514949020, 269455206, 211555235, 541913607, 110928789, 792085550, 734577571, 427436652, 753654844, 194452851, 505545602, 352202349, 327112155, 561250025, 768276031, 636342581, 758985283, 390985568, 263570962, 194375367, 395440200, 495840427, 58774402, 98218434, 426326706, 508172289, 153870038, 306105453, 847398190, 327447886, 78364594, 332997036, 883837624, 780351821, 798242039, 931220599, 251576138, 593257224, 838790815, 52902269, 503421841, 523967558, 813212807, 747409226, 574002128, 432487337, 235365263, 31103775, 895260314, 453465220, 180199053, 859932439, 364960946, 85070788, 617167468, 389486148, 445918510, 680415189, 818057981, 232439179, 474617272, 590255109, 142599749, 64118808, 501542620, 670494388, 716365631, 985540348, 719256170, 905126716, 711577324, 191090139, 741298133, 170161685, 176972818, 177189726, 932226259, 631528724, 52089355, 486017688, 740460553, 997735237, 760123498, 553932613, 117747134, 161938075, 74399538, 960947525, 59269061, 633412512, 972348172, 167509535, 312357740, 568480786, 209674666, 652764959, 479611869, 789666363, 221193008, 647337833, 175735089, 271748430, 955155222, 340369678, 561837903, 936456519, 69196640, 330737103, 765929344, 653780800, 268635731, 647452265, 862903616, 337490707, 682267666, 937869467, 193371976, 158297483, 512602206, 890702600, 501716782, 980795913, 235499200, 310692588, 854514569, 512199021, 876598929, 609346426, 795761691, 215361076, 867754311, 293637541, 101127129, 878403716, 932412582, 520160573, 896453637, 986067302, 890246247, 987127082, 891485096, 41910843, 841030374, 306347047, 731922429, 834480153, 388005387, 267583246, 446779090, 847363676, 197066135, 768542647, 304404255, 765609402, 604365586, 90280380, 33947293, 295572588, 927772712, 575031317, 841815358, 669801948, 895931334, 666251251, 447271358, 339150153, 439809087, 636966421, 95073189, 120094864, 724216358, 648466512, 986214841, 595756994, 764585991, 797784250, 474708845, 489984034, 950834912, 280187025, 334690121, 311728535, 898742882, 827078115, 243072688, 160602464, 89648214, 757439879, 100451964, 694253263, 632124432, 459858292, 788649791, 293541649, 563865342, 923252753, 634484805, 322121510, 93809928, 345839538, 662243652, 456525176, 623974163, 785269305, 883270483, 76633116, 722777797, 527318058, 861039004, 680285242, 788678069, 203894403, 396236442, 372152348, 298957776, 573257661, 781041646, 518381883, 579993382, 44808192, 45109649, 493383209, 495025827, 892958739, 740817392, 951458279, 815011652, 330123825, 179500137, 139072840, 562610724, 218756925, 35859717, 393250151, 400482915, 334959185, 258768509, 667717124, 951484453, 334834725, 741240644, 899249177, 327641080, 601496982, 388984457, 105618491, 340997278, 423756896, 267133162, 856431025, 907599362, 746571907, 481426513, 548514573, 173662619, 468385700, 19040270, 351548924, 994224480, 232805696, 727821318, 877223237, 792869903, 921258903, 706694601, 610447468, 224967562, 414877357, 747172222, 222822165, 661604802, 565788675, 204464935, 991018823, 663320318, 914249489, 274261090, 558532339, 988264704, 899150808, 273016201, 883776958, 929684339, 750331359, 387490482, 471376870, 4053263, 788329502, 944166978, 507839185, 82845531, 432931248, 930749176, 871084887, 317753262, 596219785, 252234046, 570869638, 477302307, 532492662, 300727276, 43884252, 42304032, 408076532, 273926677, 483758410, 20198442, 858005202, 880633274, 966933985, 586522266, 319203090, 221985826, 824306772, 974977024, 788528887, 472311030, 365740922, 383050445, 633346853, 861784603, 518183650, 817473830, 176401317, 366278232, 564913272, 686170203, 675190887, 337693240, 143185043, 778292312, 679519713, 921758497, 576385503, 580218368, 542333146, 329396899, 695513889, 909191076, 526984661, 976129039, 154175602, 905568777, 764017252, 510986855, 523706197, 700014178, 118039873, 795143461, 610107704, 721914976, 118570932, 117794381, 704610359, 889180603, 124792373, 359394026, 809447775, 785449026, 844132069, 339380796, 867992771, 411744195, 393904595, 194894207, 874153231, 185524799, 878957794, 913051145, 532607726, 379002718, 439219160, 931097818, 559998096, 136201558, 372537584, 138104349, 138964900, 563850467, 449537477, 796958697, 158059824, 407934489, 174240304, 933645503, 94807416, 618651469, 258850185, 756310129, 418751161, 551198232, 895387254, 665580405, 12182957, 764178494, 434565709, 550431683, 560104936, 304856602, 658879860, 754218462, 520641117, 839060875, 867092916, 448586770, 725567540, 457885159, 862153220, 320392649, 608161970, 717286295, 889436722, 707629508, 887288338, 640124949, 246461851, 447247431, 61944920, 458072743, 22059319, 760585101, 812992620, 94208476, 179234940, 154388424, 746816071, 868196869, 101689701, 104237654, 169539607, 449668579, 243755662, 1538021, 811676805, 453334006, 205183057, 274742668, 667838343, 111946884, 962125160, 169152381, 164757107, 820778605, 40608265, 833933113, 597760325, 733832682, 34725313, 750514380, 648265931, 39369503, 423306694, 716955111, 599282441, 843946040, 590277616, 978431349, 468703128, 319783020, 968032855, 121112679, 322647094, 532683175, 785682928, 563305425, 807831834, 993492168, 280461808, 110696119, 18897288, 439523902, 568699607, 133201213, 670941319, 84754153, 482824980, 595587070, 177164200, 296358001, 604354785, 82842106, 433923044, 915933477, 448880627, 60737025, 418176514, 362936073, 563805258, 68570912, 404353998, 186126991, 823995182, 172728738, 374855658, 774614148, 120429944, 126745046, 931336076, 820478542, 980493003, 113784768, 717055260, 72269742, 42644502, 361627105, 567929817, 703348957, 946532162, 730642775, 896565553, 245687784, 678886682, 796306620, 618830891, 70806116, 880226499, 743923745, 402031437, 585925331, 546959035, 694849664, 450106285, 498504148, 164995692, 97797831, 201780478, 101383412, 837310657, 452459656, 80216301, 958261341, 757410412, 388221532, 299764838, 191388302, 107825463, 933699557, 946349222, 189743058, 905413045, 618057814, 595168624, 523627016, 701547170, 742272892, 523647710, 893526925, 974602185, 597983769, 752832519, 199225694, 398649835, 390751544, 126116328, 133778449, 844667619, 483019918, 921255724, 963507932, 531012367, 107268093, 619054525, 669392857, 754911136, 749025261, 84945136, 581497114, 82766065, 207819127, 638553163, 92480875, 384365757, 323053687, 5335950, 908997439, 398885318, 542185510, 508718168, 73800825, 936205007, 413642617, 440819321, 216651241, 579426546, 168774394, 637442179, 952984013, 526897232, 719833277, 592277078, 919016023, 589278432, 48295221, 928897773, 117537829, 220773587, 761919328, 37246179, 481792597, 518672953, 560915046, 22325812, 496384293, 129782091, 333684424, 277361475, 413749111, 307133884, 17027839, 948783130, 90125010, 23914083, 686549723, 758164487, 904698606, 276543444, 507287692, 774063218, 523462132, 996476226, 727343657, 632688181, 982638228, 945078904, 694865378, 512178539, 65038175, 166185516, 973025316, 31273959, 719119487, 709316127, 988643972, 659087929, 442618137, 694169527, 144824914, 355679957, 954492231, 42099116, 664835628, 784690056, 824238517, 609449964, 282716011, 878462139, 751283952, 603802723, 984556230, 402594395, 767982778, 204132253, 817564239, 841983787, 708680912, 507695129, 193801617, 315453446, 27054988, 435496777, 288750174, 452232102, 262241270, 781900442, 701528289, 210605476, 809292716, 244573828, 143639996, 796164060, 268977976, 928924013, 143457554, 337780952, 697284710, 629748888, 488316226, 821506584, 972262198, 449040254, 555479004, 684372077, 370007796, 895106216, 576169014, 432416051, 693259707, 904504326, 373788784, 187447211, 576781174, 42031404, 212913198, 323940113, 545675325, 66740570, 768153458, 177686137, 76583477, 433055702, 306097592, 351369454, 26100261, 338661445, 552403268, 444444517, 361464398, 745902080, 368071382, 501669490, 881056461, 633986960, 92376521, 447312538, 322056866, 952126970, 132907180, 779437822, 82777802, 399448521, 884216749, 755285575, 294926371, 583851237, 576562945, 363823158, 450600075, 424313903, 786756845, 317550027, 247481030, 676669472, 739666372, 222690360, 374740931, 135111876, 831106891, 173398375, 577965686, 270699985, 58752635, 177661348, 285790708, 594167835, 460062379, 573540212, 749436637, 67410690, 317300888, 271813820, 576195472, 605875333, 712345746, 648327215, 43543676, 36471202, 521878399, 852729858, 17090846, 599089449, 442278455, 32560312, 613125160, 297078716, 860258691, 811901814, 360235499, 621345610, 432328080, 940026951, 730048267, 330424156, 17400432, 844934671, 14136916, 717972741, 55003792, 820767376, 221871409, 622212918, 528119283, 82241353, 61944471, 527338055, 463757456, 95879940, 952855769, 210255149, 443105133, 83188365, 785569758, 243451089, 99791535, 946058739, 28283302, 232002549, 484217223, 351357885, 399213220, 967524989, 671336735, 293833515, 344303480, 125877988, 538086241, 472786797, 821425810, 319486050, 263760956, 237070956, 981210255, 295774140, 34348328, 439119445, 334466056, 144458817, 954458062, 131551735, 564453968] 259451167))37 38 39-- Grouping test cases40tests :: Test41tests = TestList [TestLabel "Test1" test1, TestLabel "Test2" test2, TestLabel "Test3" test3, TestLabel "Test4" test4, TestLabel "Test5" test5, TestLabel "Test6" test6, TestLabel "Test7" test7, TestLabel "Test8" test8, TestLabel "Test9" test9]42 43-- Running the tests44main :: IO Counts45main = runTestTT tests46