FPEvalDataset/LeetCodeProblem
0302
1{2 "id": 3212,3 "name": "count_the_number_of_good_partitions",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/count-the-number-of-good-partitions/",6 "date": "2023-12-03 00:00:00",7 "task_description": "You are given a **0-indexed** array `nums` consisting of **positive** integers. A partition of an array into one or more **contiguous** subarrays is called **good** if no two subarrays contain the same number. Return _the **total number** of good partitions of _`nums`. Since the answer may be large, return it **modulo** `109 + 7`. **Example 1:** ``` **Input:** nums = [1,2,3,4] **Output:** 8 **Explanation:** The 8 possible good partitions are: ([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]), and ([1,2,3,4]). ``` **Example 2:** ``` **Input:** nums = [1,1,1,1] **Output:** 1 **Explanation:** The only possible good partition is: ([1,1,1,1]). ``` **Example 3:** ``` **Input:** nums = [1,2,1,3] **Output:** 2 **Explanation:** The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]). ``` **Constraints:** `1 <= nums.length <= 105` `1 <= nums[i] <= 109`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,3,4]",12 "output": "8 "13 },14 {15 "label": "Example 2",16 "input": "nums = [1,1,1,1]",17 "output": "1 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,2,1,3]",22 "output": "2 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 28,29 50,30 15,31 47,32 24,33 41,34 735 ],36 "output": 6437 },38 {39 "input": [40 74,41 76,42 78,43 76,44 89,45 16,46 67,47 87,48 74,49 19,50 43,51 1,52 1153 ],54 "output": 1655 },56 {57 "input": [58 349,59 980,60 509,61 219,62 341,63 832,64 346,65 529,66 398,67 497,68 431,69 35,70 245,71 924,72 103,73 681,74 721,75 162,76 297,77 165,78 435,79 927,80 126,81 765,82 133,83 88484 ],85 "output": 3355443286 },87 {88 "input": [89 5426,90 1257,91 9816,92 6158,93 9688,94 2848,95 6946,96 1111,97 9793,98 5226,99 8764,100 1870,101 9908,102 4304,103 9719,104 4961,105 7933,106 1880,107 6274,108 3680,109 2558,110 6370,111 1838,112 7163,113 1138,114 7556,115 9336,116 9548,117 7724,118 5784,119 6582,120 890,121 662,122 5617,123 2927,124 8147,125 6492,126 8793,127 7883128 ],129 "output": 877905026130 },131 {132 "input": [133 646598860,134 561431443,135 64916140,136 421279420,137 451842384,138 594684448,139 582366260,140 27742485,141 93020289,142 106103974,143 513061273,144 721754696,145 153172064,146 353126065,147 374775577,148 104189311,149 864111096,150 556850556,151 340927679,152 783370935,153 822570236,154 367036597,155 157415189,156 648213543,157 701698892,158 282022989,159 635919531,160 828245737,161 56780889,162 447539194,163 168487111,164 950673160,165 449820444,166 678840408,167 823530950,168 671283459,169 960267252,170 903172783,171 724775881,172 999814473,173 60837578,174 75672781,175 428490722,176 199431833,177 979826841,178 366776607,179 514472164,180 848893455,181 759635805,182 803995233,183 61977288,184 572612690,185 30508839,186 924681844,187 981210037,188 648508864,189 1033117,190 702288319,191 580003200,192 63263702,193 361842506,194 506347905,195 313331950,196 656900167,197 801761224,198 173732917,199 302971462,200 186828228,201 623202559,202 731243296,203 266668967,204 685319871,205 368904344,206 139181245,207 773533659,208 910640203,209 605714169,210 73097515,211 402805426,212 956422318,213 356848685,214 495087039,215 953975385,216 730159090,217 478084045,218 154737293,219 208488535,220 29020826,221 577569563,222 775510527,223 866413307,224 271128006,225 604473433,226 783347583,227 225804379,228 792284653,229 265737415,230 636550668,231 393191952,232 752427814,233 121865619,234 919357094,235 444117907,236 167516452,237 141826710,238 797187870,239 726331991,240 294170032,241 282050193,242 506680002,243 925393857,244 618867682,245 393893355,246 449481371,247 335662720,248 298302723,249 589277029,250 387213976,251 219807097,252 632455257,253 29573390,254 564361805,255 336161152,256 778768865,257 365175218,258 645991443,259 594457460,260 487674572,261 488040989,262 170889721,263 826376882,264 944081090,265 786030986,266 938084978,267 388598284,268 975457003,269 356741001,270 401798998,271 450015817,272 725912934,273 392489037,274 486036282,275 23031808,276 662782646,277 757747927,278 930143553,279 936966293,280 568309187,281 863742844,282 267141491,283 290895799,284 50733247,285 533742313,286 450781796,287 358014205,288 639763440,289 899135929,290 236459464,291 664768670,292 942791969,293 697419600,294 451079615,295 186188020,296 323054620,297 315616671,298 172909622,299 267352036,300 375052215,301 692979441,302 754218325,303 558553311,304 268230623,305 66471027,306 860722540,307 91061433,308 182857118,309 288932649,310 821748012,311 279902163,312 240659674,313 666328712,314 205939758,315 150617193,316 548125933,317 395140692,318 464785200,319 649515367,320 325265981,321 901224570,322 79780298,323 294941003,324 692539229,325 675954204,326 152375239,327 428791371,328 369330146,329 883598666,330 880493755,331 503055362,332 501153500,333 943698304,334 842502420,335 762733942,336 370506982,337 680225874,338 720090609,339 846318481,340 754191956,341 596818941,342 592054521,343 935386592,344 781827016,345 669350088,346 133907262,347 7748224,348 589346923,349 527989497,350 53459541,351 860504864,352 957698552,353 860077646,354 948014601,355 979348406,356 942314738,357 309652035,358 305289328,359 407301302,360 197044777,361 971313449,362 415084985,363 140409995,364 15406772,365 454465184,366 862377159,367 194036760,368 665740652,369 459267558,370 194827282,371 896461246,372 448229652,373 569968699,374 948834263,375 715830693,376 398480584,377 830738048,378 254655614,379 225303890,380 807588604,381 861210996,382 637886093,383 875051955,384 431505304,385 470887395,386 326993226,387 719148740,388 223196115,389 429254437,390 127658626,391 110202436,392 153204792,393 209446863,394 727591199,395 712182081,396 552041916,397 559814945,398 438543307,399 769109024,400 297578510,401 47564072,402 267405085,403 732843571,404 921673976,405 742999084,406 711386418,407 269457723,408 597943530,409 499027844,410 938527716,411 462782581,412 131417545,413 365973982,414 237295954,415 464043496,416 8554855,417 777078699,418 829596050,419 733179153,420 271060981,421 459756043,422 423524229,423 701363848,424 676942352,425 35594343,426 786057750,427 619877448,428 421446196,429 914525072,430 268089649,431 434636526,432 285794969,433 557241247,434 652915857,435 912154208,436 529311054,437 829015170,438 985751164,439 694474052,440 769253416,441 745889958,442 936668994,443 94514222,444 624111644,445 63866335,446 556684126,447 732439285,448 493552963,449 706113318,450 390462268,451 757236920,452 237796031,453 864143599,454 815588156,455 298762455,456 738053236,457 760239402,458 906344074,459 493300664,460 234902570,461 614768617,462 733514327,463 192276640,464 833041946,465 131911699,466 247813366,467 566384993,468 464193956,469 534325733,470 869147570,471 382040961,472 867337803,473 883640326,474 152928246,475 758979402,476 474642580,477 400259228,478 239121811,479 58474591,480 753012801,481 977489367,482 547743453,483 460912179,484 967320817,485 778438902,486 350795708,487 694852972,488 551837153,489 275739941,490 273140526,491 975499989,492 994888460,493 247024976,494 166622897,495 768488070,496 637891118,497 52925717,498 469142733,499 630599833,500 721516212,501 170244101,502 495866797,503 894804312,504 898598197,505 100898503,506 702890355,507 546996955,508 265516350,509 199770576,510 672371168,511 515505328,512 411620565,513 120445336,514 494629921,515 134108053,516 896598008,517 878478807,518 190097030,519 634637867,520 136099281,521 456430246,522 595053063,523 698167916,524 700116519,525 354275527,526 948845720,527 784796941,528 935726221,529 897885655,530 649351280,531 868489627,532 29376188,533 61855630,534 804929924,535 325875239,536 137190547,537 751934041,538 302995994,539 64421391,540 689981190,541 860879730,542 251143327,543 170641620,544 394946611,545 225374246,546 841359100,547 86913651,548 655002107,549 787840351,550 688650062,551 266138659,552 224351716,553 211050975,554 610976613,555 687244935,556 63995121,557 407361147,558 637061220,559 802652469,560 262769007,561 931129770,562 578162293,563 447119078,564 113689047,565 737766720,566 579643629,567 277384087,568 545444526,569 119814803,570 621059879,571 731463689,572 249871940,573 390564916,574 736070334,575 63400260,576 367983052,577 126380465,578 499498570,579 836220682,580 369130059,581 970927077,582 721101650,583 498761158,584 278843915,585 789553665,586 814583455,587 374713768,588 383706826,589 893255023,590 275669903,591 412746162,592 86762844,593 152073485,594 469451080,595 350570433,596 971325579,597 806944043,598 890699360,599 703477032,600 244215897,601 941156870,602 831287653,603 816041316,604 690616012,605 913168939,606 505295130,607 515562725,608 923381148,609 83043215,610 862457990,611 668716120,612 22178453,613 139648597,614 615286280,615 829412640,616 651934644,617 541549089,618 695171500,619 892596737,620 936385554,621 163010070,622 742258298,623 320401349,624 847683111,625 370013033,626 434945310,627 997258944,628 659386449,629 794539426,630 97487268,631 732964370,632 530182896,633 802697685,634 272544280,635 532210920,636 20364019,637 261088773,638 140519583,639 193701216,640 194082490,641 912155970,642 804233078,643 507858306,644 866816933,645 907846804,646 561261700,647 456189549,648 700302583,649 640329685,650 854515200,651 811147825,652 555012357,653 921682894,654 354684799,655 369037471,656 421556115,657 104276630,658 935340067,659 587724544,660 51108864,661 341953548,662 480435302,663 470295109,664 837219355,665 135201042,666 986240997,667 218658337,668 197737803,669 665313768,670 858368556,671 917592528,672 121390789,673 763611603,674 576173246,675 897564027,676 369376203,677 924162561,678 614452873,679 227362307,680 592430499,681 828585567,682 715015735,683 927926951,684 117333245,685 187904891,686 819191202,687 336943301,688 27925132,689 318576342,690 775207664,691 804725759,692 226581283,693 959819721,694 944118863,695 192527149,696 407028733,697 19978792,698 155515500,699 354906461,700 38405535,701 326470035,702 143808915,703 359741853,704 201471573,705 678785890,706 884685933,707 989762702,708 830592977,709 712914461,710 838249978,711 215741123,712 534811763,713 31519934,714 15406299,715 945688314,716 322412894,717 223244997,718 63400029,719 730967421,720 595994074,721 651791466,722 28537733,723 902095458,724 115989171,725 601031880,726 239858147,727 167774718,728 311045845,729 30834801,730 225357350,731 443150585,732 811172524,733 202019335,734 924615559,735 660096283,736 448985942,737 550621991,738 201030021,739 672609734,740 913201732,741 172205564,742 199415197,743 335089270,744 438454310,745 277914220,746 17155097,747 624725299,748 442227134,749 381002374,750 309136338,751 196148030,752 792885406,753 240878363,754 816449386,755 118672413,756 194708103,757 401444455,758 723402756,759 196417782,760 158804348,761 647139954,762 429145759,763 264046141,764 800822301,765 325871536,766 787818437,767 272394937,768 309973618,769 309367838,770 917029155,771 65690020,772 407322084,773 266554765,774 628010184,775 487040353,776 359304143,777 946784278,778 253359800,779 765894637,780 411974524,781 738952789,782 807211615,783 844801446,784 724265430,785 446671073,786 569900476,787 89940244,788 568079443,789 976537578,790 870728969,791 750028876,792 693843937,793 962705570,794 274981028,795 223847953,796 409044777,797 144619188,798 563683444,799 270425351,800 983657209,801 586083515,802 645715403,803 75146343,804 897698555,805 48986668,806 823676069,807 770088462,808 667456337,809 33644706,810 412210999,811 768047210,812 32455228,813 542890745,814 315463282,815 127028958,816 604964588,817 456924979,818 72970952,819 356452803,820 939083905,821 442753522,822 874850469,823 868883281,824 300064692,825 208942863,826 223707342,827 374643847,828 268895355,829 469880247,830 56542565,831 405037672,832 994594060,833 440358993,834 829529938,835 275832578,836 673647373,837 943621500,838 212277765,839 377721469,840 220315520,841 462361,842 694546801,843 25302239,844 216863174,845 775503249,846 654641307,847 916645968,848 948099465,849 856944600,850 465802293,851 368061923,852 622642751,853 604382346,854 617509002,855 354523577,856 897756199,857 947276868,858 2411751,859 938495747,860 155533046,861 639908829,862 316687216,863 980698086,864 851611246,865 415154679,866 884032067,867 93979504,868 375563637,869 847041700,870 56489014,871 870797839,872 441872686,873 575983937,874 116637110,875 725086171,876 549557350,877 783529594,878 609259789,879 870027445,880 127370559,881 20641895,882 120310894,883 558061400,884 165256784,885 109860709,886 706706532,887 318678874,888 721639292,889 916613327,890 117309609,891 805901246,892 737674057,893 281410289,894 468252374,895 514236277,896 723443088,897 679087530,898 975044299,899 395287581,900 372319670,901 920787101,902 55096451,903 318528876,904 667045175,905 640617769,906 220616043,907 918849457,908 615245443,909 693400253,910 456402342,911 540302822,912 779293797,913 704936028,914 236736073,915 753741983,916 28875304,917 799637357,918 692755383,919 289340760,920 633941063,921 753043539,922 137818621,923 612348403,924 110792782,925 829789407,926 138441374,927 583267682,928 437435843,929 957909431,930 381854717,931 385729545,932 30587630,933 839604378,934 508069598,935 751537528,936 76577543,937 420818846,938 559349595,939 942156144,940 833019797,941 754730377,942 27980613,943 884916903,944 88095532,945 994618333,946 916130562,947 363606957,948 697350400,949 240213784,950 433833326,951 683575490,952 545642046,953 498915692,954 351719472,955 675504625,956 709564089,957 633444385,958 366105328,959 480544842,960 376499046,961 371003512,962 588703953,963 169245656,964 404293158,965 581876690,966 998563903,967 1493199,968 825930939,969 416515555,970 277694072,971 323748736,972 401241201,973 463185431,974 988727663,975 356634919,976 573339390,977 955818365,978 580290077,979 445074532,980 639698987,981 10893906,982 524274707,983 112030412,984 9785032,985 106997903,986 504178023,987 502162806,988 786554820,989 192355213,990 847071475,991 444135672,992 561861957,993 99327785,994 779894393,995 415919723,996 228771771,997 638512473,998 878654443,999 302329264,1000 592706152,1001 369803258,1002 236697573,1003 12174757,1004 143723128,1005 423776518,1006 57302195,1007 979747540,1008 333899115,1009 983787734,1010 563267890,1011 592104523,1012 668737913,1013 334995162,1014 402863760,1015 906190705,1016 418706164,1017 650220151,1018 70527344,1019 469928387,1020 510850257,1021 18564163,1022 511023650,1023 926937917,1024 759663006,1025 529251025,1026 468358641,1027 143751369,1028 510672452,1029 554412281,1030 699010686,1031 979564174,1032 251323972,1033 498157758,1034 336863523,1035 663027360,1036 240043312,1037 234816946,1038 824432238,1039 415353798,1040 234768380,1041 611434972,1042 527511735,1043 907518620,1044 318539064,1045 203847227,1046 633414896,1047 470813056,1048 255297291,1049 120717490,1050 778632530,1051 169346592,1052 17432585,1053 627724091,1054 902989482,1055 919082420,1056 975748375,1057 276350232,1058 237035685,1059 327903728,1060 871110644,1061 200728344,1062 207963083,1063 865677534,1064 25945540,1065 543440428,1066 993179659,1067 773673464,1068 491931977,1069 443907380,1070 204741759,1071 160843921,1072 161533007,1073 91471274,1074 81114835,1075 536097974,1076 14650867,1077 810709393,1078 386080370,1079 550886346,1080 473091384,1081 800521917,1082 590980260,1083 664565521,1084 269113539,1085 785975441,1086 319714686,1087 20541927,1088 372794099,1089 596539860,1090 178401804,1091 675629222,1092 783738189,1093 881582506,1094 377386850,1095 971781977,1096 620473823,1097 549272706,1098 678823863,1099 6452705,1100 970809561,1101 97665126,1102 417774364,1103 808737858,1104 422478838,1105 689494648,1106 349519509,1107 215656621,1108 355837878,1109 372858930,1110 160856723,1111 78796563,1112 642101847,1113 435615249,1114 759342732,1115 931711883,1116 501341887,1117 685333029,1118 767122813,1119 275728783,1120 659472807,1121 234345654,1122 923579940,1123 605436992,1124 494442621,1125 547036603,1126 636158469,1127 512335528,1128 420475600,1129 16298223,1130 467295566,1131 732497576,1132 633257491,1133 823749068,1134 917683248,1135 346663958,1136 301683339,1137 448623240,1138 122948676,1139 978955091,1140 105661712,1141 814968712,1142 391765998,1143 851659049,1144 507244512,1145 137617650,1146 524466227,1147 758249705,1148 383578398,1149 697168958,1150 175737849,1151 237169673,1152 83303593,1153 520546402,1154 248627573,1155 252014002,1156 787628347,1157 691623083,1158 273729350,1159 635719396,1160 130387234,1161 193529064,1162 744502164,1163 454714277,1164 849975793,1165 9951909,1166 875440692,1167 128385717,1168 778506685,1169 922419361,1170 123638840,1171 613519873,1172 716248373,1173 314113379,1174 625798894,1175 726434809,1176 69177404,1177 575802945,1178 268327636,1179 496884061,1180 634312847,1181 304252233,1182 641822068,1183 22742188,1184 131895761,1185 169898911,1186 163254240,1187 693251685,1188 194901855,1189 199724193,1190 969366770,1191 757436146,1192 19980943,1193 348391854,1194 384656055,1195 51198718,1196 178827252,1197 148135555,1198 864005642,1199 260587738,1200 146019046,