3013. Divide an Array Into Subarrays With Minimum Cost II

#php #leetcode #algorithms #programming
Difficulty: Hard
Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue), Biweekly Contest 122
You are given a 0-indexed array of integers nums of length n, and two positive integers k and dist.
The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.
You need to divide nums into k disjoint contiguous subarrays¹, such that the difference between the starting index of the second subarray and the starting index of the kᵗʰ subarray should be less than or equal to dist. In other words, if you divide nums into the subarrays nums[0..(i₁ - 1)], nums[i₁..(i₂ - 1)], ..., nums[iₖ₋₁..(n - 1)], then iₖ₋₁ - i₁ <= dist.
Return the minimum possible sum of the cost of these subarrays.
Example 1:
Input: nums = [1,3,2,6,4,2], k = 3, dist = 3
Output: 5
Explanation: The best possible way to divide nums into 3 subarrays is: [1,3], [2,6,4], and [2]. This choice is valid because iₖ₋₁ - i₁ is 5 - 2 = 3 which is equal to dist. The total cost is nums[0] + nums[2] + nums[5] which is 1 + 2 + 2 = 5.
- It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 5.
Example 2:
Input: nums = [10,1,2,2,2,1], k = 4, dist = 3
Output: 15
Explanation: The best possible way to divide nums into 4 subarrays is: [10], [1], [2], and [2,2,1]. This choice is valid because iₖ₋₁ - i₁ is 3 - 1 = 2 which is less than dist. The total cost is nums[0] + nums[1] + nums[2] + nums[3] which is 10 + 1 + 2 + 2 = 15.
- The division [10], [1], [2,2,2], and [1] is not valid, because the difference between iₖ₋₁ and i₁ is 5 - 1 = 4, which is greater than dist.
- It can be shown that there is no possible way to divide nums into 4 subarrays at a cost lower than 15.
Example 3:
Input: nums = [10,8,18,9], k = 3, dist = 1
Output: 36
Explanation: The best possible way to divide nums into 4 subarrays is: [10], [8], and [18,9]. This choice is valid because iₖ₋₁ - i₁ is 2 - 1 = 1 which is equal to dist.The total cost is nums[0] + nums[1] + nums[2] which is 10 + 8 + 18 = 36.
- The division [10], [8,18], and [9] is not valid, because the difference between iₖ₋₁ and i₁ is 3 - 1 = 2, which is greater than dist.
- It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 36.
Example 4:
Input: nums = [1,6,4,7,9,6,1], k = 4, dist = 4
Output: 12
Example 5:
Input: nums = [1,5,4,6], k = 4, dist = 2
Output: 16
Constraints:
3 <= n <= 10⁵
1 <= nums[i] <= 10⁹
3 <= k <= n
k - 2 <= dist <= n - 2
Hint:
For each i > 0, try each nums[i] as the first element of the second subarray. We need to find the sum of k - 2 smallest values in the index range [i + 1, min(i + dist, n - 1)].
Typically, we use a max heap to maintain the top k - 2 smallest values dynamically. Here we also have a sliding window, which is the index range [i + 1, min(i + dist, n - 1)]. We can use another min heap to put unselected values for future use.
Update the two heaps when iteration over i. Ordered/Tree sets are also a good choice since we have to delete elements.
If the max heap’s size is less than k - 2, use the min heap’s value to fill it. If the maximum value in the max heap is larger than the smallest value in the min heap, swap them in the two heaps.
Solution:
We are given an array nums of length n, and we need to divide it into k disjoint contiguous subarrays such that if the starting indices of the subarrays are 0, i₁, i₂, ..., iₖ₋₁, then iₖ₋₁ - i₁ <= dist. We want the minimum sum of the first elements of each subarray, which is nums[0] + nums[i₁] + nums[i₂] + ... + nums[iₖ₋₁].
Approach:

Problem Restatement: We need to divide the array into k contiguous subarrays. The cost of each subarray is its first element. The division must satisfy that the difference between the starting index of the second subarray and the starting index of the last subarray is at most dist. The goal is to minimize the sum of the costs.
Key Insight: Since the first subarray always starts at index 0, its cost nums[0] is fixed. We need to choose k-1 additional starting indices i₁, i₂, ..., iₖ₋₁ such that:
- 1 ≤ i₁ < i₂ < ... < iₖ₋₁ ≤ n-1
- iₖ₋₁ - i₁ ≤ dist We want to minimize nums[i₁] + nums[i₂] + ... + nums[iₖ₋₁].
Reduction: For each possible first chosen index m = i₁, we must choose k-2 additional indices from the window [m+1, m+dist] (clamped to array bounds). To minimize the sum, we choose the smallest k-2 values in that window. Thus, the cost for a fixed m is nums[m] + sum_of_smallest_{k-2}(window). The overall minimum cost is nums[0] + min_{m} (nums[m] + sum_of_smallest_{k-2}(window)).
Sliding Window with Two Heaps: We need to compute the sum of the smallest k-2 values in a sliding window [m+1, m+dist] for each m from 1 to n - (k-1). To do this efficiently, we maintain:
- A max-heap (selected) storing the current k-2 smallest values in the window.
- A min-heap (candidates) storing the remaining values in the window.
- We also track the sum of values in selected and use hash maps for lazy deletion.
Algorithm Steps:
- Initialize the window for m = 1 (indices [2, min(1+dist, n-1)]). Insert all elements into candidates, then move the smallest k-2 elements to selected.
- For each m from 1 to n - (k-1):
  - Compute the cost for this m as nums[m] + sum(selected).
  - Update the global minimum.
  - If m is not the last, slide the window:
    - Remove the element at index m+1 (left boundary of the current window).
    - Add the element at index m+1+dist (new right boundary) if within bounds.
  - Adjust the heaps to maintain the invariant that selected contains exactly the smallest k-2 values in the current window.
- Return nums[0] + min_cost.
Heap Management:
- When removing an element, we lazily decrement its count; during heap operations, we clean up elements with zero count.
- When adding an element, we compare it with the maximum in selected to decide where to place it.
- After each update, we balance the heaps: ensure selected has exactly k-2 elements and that the largest in selected is not greater than the smallest in candidates (swap if needed).
Let's implement this solution in PHP: 3013. Divide an Array Into Subarrays With Minimum Cost II
<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $dist
 * @return Integer
 */
function minimumCost(array $nums, int $k, int $dist): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minimumCost([1,3,2,6,4,2], 3, 3) . "\n";               // Output: 5
echo minimumCost([10,1,2,2,2,1], 4, 3) . "\n";              // Output: 15
echo minimumCost([10,8,18,9], 3, 1) . "\n";                 // Output: 36
echo minimumCost([1,6,4,7,9,6,1], 4, 4) . "\n";             // Output: 12
echo minimumCost([1,5,4,6], 4, 2) . "\n";                   // Output: 16
$nums = [355316569,344623789,714178379,227573947,269872416,529400023,927795017,819139,989101715,195525,935035625,924059449,890862929,312677730,821734683,675959860,937653,912762114,686410476,861745191,984331952,769282976,174720,54270,810730649,145647624,910521711,578679074,394182,523828514,290990430,852834,580681469,607471672,481807044,190788304,930551,782968226,412911512,758926787,376645,667304,386455276,333741713,970661,350558575,319317189,960118,186783161,392224367,647345746,950226,639175,534137,341338765,376242667,378524905,581796422,837602313,696183462,976417191,813173301,890871786,559860216,700770219,955013,108754499,266873,174327053,988086,649060,632178949,258406162,538702,257290775,619671304,175918,112050464,660372,657765118,597531270,173128161,225482925,248061707,369191408,212684458,946213131,688304347,31732,242257469,489461358,905098760,672625036,335607315,528667100,800202662,339178165,697642054,354645761,268562881,875098,384561522,282083111,812945019,827963481,166691620,397010765,907035537,903132966,383071421,872056131,210022195,954301813,882529287,810806140,686119,364602833,775900362,709637,875956355,770631815,529875955,150749686,366455826,666989364,209997427,680136988,421286111,884045661,723830646,718751328,992735617,820631137,103496,809777687,989315178,557465,815087726,257064377,994813181,343067,254129548,598223104,137970053,988085716,244585,306045225,904368524,989009555,950911770,726170221,756363824,765432680,110261766,325845106,258293,763908561,198088840,568243,561398125,380517,715459093,681306171,649763445,337732829,609346124,402673,234484099,300183345,385843113,805109114,755432416,760795,992661126,780266463,480188701,919011890,849656861,329803531,111895059,244046462,696255595,314718611,208271,668937638,176660,647988,950793966,303003913,424025422,763190,520577833,246561860,608188790,582386519,934063786,310187025,129921422,357793324,426419331,617821,897690823,434990,682821619,160886,859744909,851830496,396435458,696370,584260167,135227381,175826674,134516413,837314517,17906,139775539,137241167,596844887,539033468,772551059,633487511,16272,463641288,462060012,463204260,523457889,489922702,628063,109525629,647841,166634,318446077,445221999,548816169,403833699,545360304,425494342,948311034,961815,695870603,755596097,790677387,188899,318506972,434157775,197431590,442880682,555908056,113776239,812070,501362451,574318446,924895353,805664102,232138012,514951068,166031681,956244929,535845353,785893852,432571348,700142778,702073324,534755446,806876399,657674267,560324,453824,119720181,277479729,851337312,995583429,225056,483131382,443946771,297235746,343225664,964258,549196380,274387991,344987572,594319667,326821753,870190469,653190,944221,619366,737557633,794322902,626758449,184517538,337874995,624532,568984502,985595312,682787777,661617723,535367801,704738851,703264442,538450847,141312321,714171335,694003248,437482867,279009733,764127987,160021188,187503369,944309125,904110,612574152,314325,188224775,942514449,188360720,580201402,131402,639093175,637794,561700805,975809873,697931,709043,595771390,847898,286041505,856656020,274824501,752171343,233121,361246091,576220,259359448,588936352,772220567,394067181,418297226,943850483,891216838,369181869,825926825,554938573,993681802,276433,735740281,541841024,179713041,424478419,292509754,132178,130642446,777578,310325567,480526290,533805606,592698492,403292424,825516477,105288932,321173685,874189964,413300,835489,778942538,444674454,394122875,234199772,368979962,569300799,261472670,112184623,276644,707326818,697578333,646425873,488436828,119087718,804581565,836100927,422569,339791576,786799451,221734216,354534212,888787,816797005,281300195,764017012,730042714,307100745,550553512,435547,906093019,466349784,905757818,275745,227467482,710567377,567633009,831709136,955931940,437130452,727247436,269923210,40777,429017016,243691007,651523454,924119040,289467727,184639944,391922147,386163194,465092952,505234385,284579,231197881,995125446,803014104,613404,413239,229472556,775938428,595514878,786974209,711072585,965315101,138467324,971449908,786163,128415584,375398054,270624083,144549383,923666391,664578835,410146547,474320802,179160199,467401,197266235,454098060,417440600,644486987,162958,344738173,568264584,505838222,305152,282617235,317247274,716063405,122208,932150111,732102153,922692844,679187142,364817941,976255591,62461,599547050,832691252,128440298,563873145,295014464,474687110,673045444,330719277,834770977,882923,634921090,844640243,585339,621059868,968361964,813056302,200705399,928287866,834860998,525444060,792449576,133494908,832933631,191542880,443184419,468611592,691342528,513914,366233,697337970,591837362,515985906,425359,571918043,369215399,863066315,104692195,895003069,640956892,129703715,353922239,843014787,211404283,149823324,420666011,734751156,421696307,115338329,629075794,182974003,601652005,428436355,692788600,774459242,136164,70113,695783441,900491102,154853312,114287034,125690248,878585087,595047433,441236402,420387399,527035,225948910,982159,402925037,274404394,817746945,493411789,825767527,386671,272271640,745134742,47282,570457939,284717652,504561950,784427,543870925,990054677,941193829,467659444,569393052,781659675,951338,362766124,556910813,648416,903083,803427633,545706907,443932263,554822614,232668676,740428965,991905912,484800305,398912719,886089077,589330552,384940519,851643776,763329,419541205,940119112,380373348,436386904,948029231,333196978,227717988,859566925,437207602,420357383,359236084,600544017,155041436,678736814,880853266,284197231,680202860,596472927,485629,876385937,750935,454506702,929334,335288070,356952556,314023017,246024880,803346,196074007,992833,962425460,316298033,568000213,551021120,985223,752806133,222341558,131996567,286032067,848132778,160307638,568569308,321762,750435,629606513,543779949,70483,446889293,158131,601823940,900007672,950731551,985760297,254928,486280269,256601658,324831348,236108518,90702,488176532,715079702,329825362,723300805,571540064,405648008,580018353,279930084,295696640,307541205,32608,557417152,210346634,697861,881118093,750259,551644,266656348,926153145,310874416,383317,218838500,455614937,225005350,350593,843583724,319973107,633128647,335624005,990874123,394575513,449110264,430179735,737959483,192179580,129395631,604749681,429976,227637141,225338699,887219831,780648623,438702377,140297975,538284592,425192349,45214,702832679,144630373,559099384,398286706,613146454,677372660,722454,565332841,166861868,440941,98866,769851937,927056,145555573,92458,371915287,609929,963764,465251060,589532841,645505590,648634283,218272572,846945543,758731,564954518,330995596,845268,251155126,133704901,903045,691064943,206479459,480640,192338996,661265354,217921843,302176231,868653251,992804895,174269773,997855612,828559310,541806146,862747827,601159,305257759,216991683,889776327,672882,302870117,602955902,418454769,184069935,784361382,801589565,871197,866530902,996316728,411902340,138967859,468159077,528519333,157302196,961047043,226723053,285497694,394447,745234591,349959,180807651,911689707,533874638,416765331,235962729,453182070,101165893,975271036,496308456,469434684,970553,766531561,745239898,567185056,647267742,274214,779827550,709801128,412290,192017867,44604,540802423,837187,277219,175245537,621915695,731844913,152255141,604043403,810442901,817662951,614342719,437638,641787490,690265803,784271230,908953326,150227179,782101031,617767049,296023066,633818136,681699303,10520,955774090,137149008,186465,180572599,183304188,472742820,248964410,861332096,333248790,514441815,272491667,173089744,758926528,746492790,810264580,752044691,191080380,663896077,192260402,86248,131425745,261519053,503420646,205916,701094838,660950271,793834964,947315256,810209243,357301415,421375,336830288,801287540,465669715,129223782,450764877,375260472,88082,932631955,409193889,113563503,705267054,595068093,742297250,390967300,749389963,948324650,244353843,915638329,526923,463149226,911118471,345540559,870141,530325781,791539573,416571611,856469403,900218327,219195377,281855394,549536360,311225293,664041,194268445,116078,456036,328821,840597,580073,534897691,729853725,373777548,513323153,144565829,619835,557882387,752655,171551844,476849442,381965248,699678,905977,729295404,520923,224401164,674951524,951453163,716629767,699570121,197710745,999049657,310591451,258390451,433639929,439228296,877592640,146817040,940864514,395426868,464664893,758032427,203306870,233409543,191796143,705270,40230,56984,366967754,846620,916935,704646260,235189326,275582450,964701810,507249508,354925914,126469563,220126942,996505485,627597950,933042526,473472943,582471039,144066446,605288327,572499406,686179046,383660421,550919872,213342772,509075,397232221,102505892,139859090,527701865,462253849,792798316,333492426,192316632,409696,808231992,276599693,386565696,703745571,363851382,396952028,220076461,591647238,473033942,514302,541877,306521933,162518622,466901374,540715863,765024969,925105,419865054,276146483,843812986,510970343,159855246,416604133,161210689,483673224,443166,891057302,267371617,870100228,731003677,356439992,811750047,374431795,736538622,769747294,668823569,331695717,670246383,183827496,774429042,182200890,200371849,403673040,154613903,765592875,973600799,365492853,829126847,731138348,984232408,248261273,117291836,755415445,467905393,766355775,629269,375133,756999,862538406,111944890,869765371,348427385,377169766,474061961,928233988,401550,409185052,805423790,817637539,942533072,209799,797518115,988548586,411561656,39365,235029,629388772,283303688,407227839,599301846,287026,841547,774403,585139419,828419651,543019008,807771984,110791,952010893,832318231,241790,122556608,671283027,169368210,828562,754109745,302168253,708896616,934162,555640893,822397,889058277,586133539,933331446,762876149,831550404,565423098,490867,455530824,964475319,117938053,406229732,110464349,770431795,843588597,912712268,239002180,716480444,462439997,149961193,247047496,115028486,237272815,887978514,781427804,468221,263770,875627844,289085,319895,426251780,108832,416701506,272237774,681349631,492383,123937535,909496705,707322,988095255,807667912,616225739,822200971,695514637,826379913,568797493,296633778,316531,997897387,760471550,248363269,202743001,582521764,698371150,104517444,325754,890043131,865472597,612188354,574071,166425487,832458580,639531664,196310754,910935217,232245,315576601,529505,674480338,461526421,135440977,919759580,852915223,381107245,492396998,428495905,175770,884051993,367649075,463914338,679388980,491165047,772706057,456496770,420587375,279464988,103941521,740711626,414459382,468187364,277308582,163419384,960520381,192560,782910532,148125,997208,178212295,840280293,149024631,175284540,517438290,956619260,301299733,645491735,445789481,763737,598349440,154457127,272680695,993977419,332025613,400891563,622092556,235993026,892088765,922098121,633304209,374834434,450891197,782388566,553948958,866422477,28459,386749720,268069340,889780710,109061833,724286161,545908536,897251341,400617672,449317308,328438408,399701386,498802996,796808408,570099743,812751962,555778306,180910703,981576,642860640,451143772,973236817,582412555,176425227,829838343,149648186,350928852,573076908,619887217,64181,292879055,753823691,967615208,164811414,809453983,402476491,818073638,926047563,357223694,428455264,296620412,883596,994223061,285564309,190679113,177399819,744352939,210813699,269991968,472151870,962393982,833855703,732541650,65753,976235215,679979975,870528,412027230,462066705,58366,305479798,429792522,600214,760864,508395,398384067,581012879,716110266,555571245,436744774,532098730,292333,675528102,517229789,79925,787220,382147779,788879429,245154706,418026103,115241,934434,773670,776652765,236060,454744593,146071,255908009,610707341,757662765,545799295,721509686,420520159,900534114,707890999,214834467,878461585,854655986,872827210,263626723,617786,466033805,225471,329223044,389800,932131,363932165,215294,508013573,241982,398435480,35088,905543398,328963,66370,783578441,342022610,519455,327566038,678288,966400,207435701,677802242,556644,300576498,578352481,150813,620554734,220968494,933139366,420623898,318018429,242717106,598300638,785417734,787515890,682579452,521028944,799560481,781159517,247089782,246964343,601528276,629215312,519955784,431000741,161424993,831933243,171077348,447570034,491673704,567989060,187596295,467478,887169,547722300,406644,235420615,469835667,429116639,382697163,276005,108702,822586769,680427759,703726604,972806472,446931736,163938869,926261,143114003,169629396,767891033,694246086,612208187,458184,800335,616430642,655891559,570509613,921735,954040771,819273753,368307753,597294844,133922342,949265128,821428471,819656913,512523821,494104,191766884,821139073,856403150,29533,438838278,811626,431727447,755374913,967629582,116049314,890928204,692665962,991773252,846764773,667100307,498358406,495174394,283891399,785035328,850209029,582222501,542361176,462119130,336020825,966510920,680657453,734013843,184643,291009766,108343,866075345,904167497,564237622,834853435,443025779,853727476,290557317,561682708,306239433,286434,150500445,619878527,206432868,397469362,256577662,356020554,288183,579706541,222348643,835617279,499827479,956211,983274399,973004155,340222,102421,950817,328054688,806109967,144546611,312653990,600228028,635013248,534285705,113341128,766156582,718949322,295755627,838840341,525962313,698414959,487073054,787937785,260314250,884012524,821971756,572587871,185381274,377541,478218,791251886,861171999,367126,887781892,908916451,194715,542409304,608746,697632,389173727,468519019,726268166,404880493,286569671,438114473,784489215,711165993,744946834,664028,342258058,970681433,787376705,501506,915995008,513699559,515303358,693411905,537721,289100440,454414366,279626198,321805572,628746657,455801,602659670,228824667,766376725,989475987,789915386,573933579,667792954,830472961,929386167,510212150,186554391,712112,880173012,761404060,607736306,344741729,507997378,636049,918356344,31290,581466262,16667,681339235,913859,992785071,368016309,333237699,252300833,997011462,731957472,694296532,975839549,935627622,187494582,319633,185275,842163505,807158567,847712190,567026660,851208555,938446298,403084449,330041853,881022767,402339974,364761434,962779788,948006907,499387109,424165279,451039480,751330888,158071,690692092,187352053,776710356,672039345,804874230,517432616,246766606,454000,332885,460455309,892134,422314232,422576522,463728666,295938004,533102809,600932835,712940381,264818220,251253643,643774297,937496,431499015,592541,195196313,683057119,938371156,503435542,838888,368359,705403202,402146,911335,366427803,943407994,153341,402716100,264169850,716885674,75240,863188728,315814752,697761,617695085,558995833,420510,865233,606976739,222952191,978693138,998382863,135323653,273723947,789404626,188671,845076864,937232,917439496,467551207,588488295,99904,376339496,652981038,561687380,545919,778154513,351497482,641630261,528543732,452532,855778,137117834,399487251,232586051,140394136,129781671,529448832,249322198,950723093,975738400,706677796,992759758,417812474,982754776,214235,606525755,895594105,722531874,285743441,999129497,545292815,26149,502372024,708611087,219622464,984268992,506711,330109337,480253281,927367,285270345,530665,517737222,80676,328927207,987158372,321996471,260105557,606950,605289226,42926,329275211,215717129,786068139,251720592,715149,484158,169218122,364960821,84068,391027617,960356,370983765,135578,173587,169839716,630946807,357530,713684606,815650064,288825306,175276589,860842593,161637,152485572,901350963,785614865,359647600,646358403,467859627,933439,178865878,963474,385899,555986028,750864600,997666813,114947807,963209,343587044,416663645,192353394,150174107,139138894,380658771,802851312,286238,896910306,304328020,391634600,439538085,480808,962180228,238042700,876596,471027832,437975,907846715,852641244,224350899,135378521,891709166,480836249,373214970,546811377,795672508,588101340,295459255,594915,464587,897617,234809072,301759638,150768499,496544992,403319072,986498158,912561140,889962886,287940775,989335635,819793177,429196966,879602131,671685939,675825542,873424949,668818668,725005577,806020512,427910303,842427497,997388673,621499,463871496,584007282,975141878,562486978,942681528,709003875,519898682,204157833,89256,911530263,790201361,911182,885987712,202508,567641668,869431909,329019,757545950,977670071,713645391,671330964,530609361,933009850,469491,543365460,921360628,182222440,510153122,958041312,255811476,920069665,790481023,106187890,225501642,560979742,211528839,384468,791027023,985105988,345722975,707485021,715728,335350567,565891057,208498,285906167,352086969,125324963,743070,991795,868253318,695769114,852254584,420633491,55360,434331151,933083960,639003,91492,161168,987976580,494672,733935260,216212501,939404,827538,642109541,451964632,456894249,211372923,847484,235788878,753173037,374549645,672491043,121004425,176504629,142874546,388061,792169961,273081883,679377878,735600337,66273,691519259,889239595,272114822,608296292,314335851,433731608,831861028,154961397,393533240,272078208,999296190,173636391,65361,780675,217036997,472830777,826301,862866478,546528,861090783,234101415,385419747,376762436,277684,856661116,125571681,545598644,718753,659362,869388233,845438,787412820,148997258,427450640,894582199,401054,962715314,623040350,694175,369150087,522130825,649364294,916211103,339754733,270623347,855474,544489,462880215,312217817,274344,961173410,267624496,905502819,996753612,888864215,551414471,994112919,17489,173886963,376504111,921889691,460643411,348319235,879597154,431210863,699955,261151996,244974985,756621609,180570940,449771,189607813,716913834,454151139,543958263,723216482,712165844,247524916,717254912,835173870,910546454,446272,922679730,505672,670019,846160537,556083320,713601508,263580840,336238698,422836971,788386,890037744,401338120,907096,618124,673072128,863952827,600765074,74393,586119824,637534994,705596232,672267285,884616973,452169688,954133535,378326188,998201389,910615,686242509,558768489,731961094,913383,737307961,121054182,972645,915436779,667734,410768,805180586,191510592,378362847,357511831,910896306,660536683,145896713,988156092,414481502,196120294,961589409,287540663,448859,732424690,459299713,397073744,595334220,619088575,377865,726702,383742106,552516772,938875194,600709276,756329970,665936827,133287,104443277,283178,773233492,633167792,150918208,839168823,945180785,558687726,217535,404118901,602631,518404371,149915,439168168,394956928,200358100,626422273,741598703,630726434,564525056,670640014,829255887,261381,449909559,315196343,44897,210949341,264468,715422,979283839,769203032,678625895,739184025,918812595,740807,496629435,280794538,602614,964841289,191335630,827728381,393291287,948790393,586724553,978112379,733679718,935877707,242649658,551793,895646206,193568115,372512749,315585140,331763224,982981233,137920727,169941531,940064994,619512693,928823728,732048494,762177395,827554388,888036846,148339962,232794849,785759883,883677694,950623700,398942,423355632,407071,284455867,482644078,562690671,499014007,758762,584280892,164693805,410932,346501552,253625402,627584988,698024631,265562872,263489171,133197060,572621970,283587,699582370,991463578,556520518,950671884,674019,878079985,710799308,335711764,679042027,507121676,798423909,846807148,654762164,162215836,577131541,934641120,523508717,933010,289456940,986132,748472,786384955,177720021,313371,141372908,387373088,780883803,157180259,298272331,120071451,755450,446876434,525349163,984171177,762087450,248588909,650076931,441338808,229150413,381274719,138115139,388575165,622458736,377480471,254942129,829319,423781627,858567,715866593,242381,650902245,601732776,699470794,659991,485534162,683074775,83832,401722,155210659,108295,771459420,994635111,138749,471362339,183825742,59719,196317920,414537,543138016,179890246,375967,367691968,857495989,708324240,577889983,606811,121209643,378855526,526804,879279054,575359,652426613,512376999,750973323,487069,158284476,908032767,959615,640590267,858224723,489046739,234570,951514501,935330501,756250843,387878741,403328124,746743519,123214898,991494909,966323861,331336,553981950,773559,446122425,671807909,637935,918022290,207918708,961484,343264434,370588752,100061483,888908977,933000926,761944136,826541528,758454561,755309831,246750,572946586,496538,409812385,813408,735983584,399642397,894633204,458953535,31507,869447354,624175802,955308180,865900258,558512482,381932009,836033326,956065768,877451675,255900868,698981594,210192404,785007,897752907,241109657,548220516,125432,660584378,339745286,464291171,778543325,244256394,515635674,153597,723915413,308498083,983796054,353715872,445823249,314482730,196906286,401190436,281208391,521324733,458654843,795192,894319219,609347178,759300268,130640,984670444,110613785,772748540,747871725,303917,999730652,891415050,488995518,398738035,176751819,705008902,419307,336635651,443813751,877165219,766478476,936933955,224733454,235510441,591545093,554117660,338036425,444528148,651709,772797256,656829,597684,941258460,435444550,370252611,967185211,101967817,424198851,482576,525368,941729608,993038836,281337,789642984,568671961,966718885,428659662,332836423,100425527,118757842,682180496,360126157,752163,368848,428232639,480863535,308515760,882244798,251920,423431,196523958,967899872,380886013,627195221,55886,970724085,786430288,804257322,288265070,941981630,549840114,797219764,154695,186584433,140611746,144290124,209066553,438690917,737695,451906327,625905091,249238718,211514,57268,218381063,954143553,220383609,675682837,346620634,616643,879784996,675046873,563331410,722764593,778260823,961235035,922455304,363291583,61904,948101799,522353938,413639739,446530730,967844038,381834994,609122112,131797307,281218601,219230476,469049495,427274760,636533,721618,315834647,516204031,829745953,675899854,340771,525980107,438996853,930089052,241487201,502980921,766633779,801461,415313127,676265952,830662704,373906482,793574,709295006,299004949,978982509,150889,144603582,277648054,210211146,909370,526860522,339695388,435028,737812309,160397839,92470,248583786,111749007,814834985,337995,416377807,839337477,437770778,913505392,613931065,445687958,532204977,201048965,437881203,556228513,898867170,908754578,51798,387813586,594663298,875222213,831159645,276818842,441864518,598420,805146536,649101,664658,598442,388070145,156454578,903326022,565186482,344712758,838030412,642794181,690975209,520216248,167597627,523446491,555805880,639630721,661310017,259228600,419418526,783647664,998420845,426615551,134092,172611463,891836139,706315187,115094399,864162994,832415023,550164,975504114,218437336,348121,752641768,703363905,823077,335252646,750124878,314262335,413951366,194852878,125859915,262369720,981026421,857690297,647066229,697586,79737,880522078,510677889,166283608,386742719,542779039,310890,804614,765474,789282,721865077,233832,153549024,449364875,781816968,841629,393399221,362517,473662632,230210343,462471017,593202262,270608639,801542869,270831557,334855243,453341982,273197950,133352488,335054703,197370627,411371599,518408709,966034,977295,875604623,105001905,923033477,202945754,861367767,168552,749744,790308296,986127151,769268132,555357299,624478351,825843643,588261390,799377202,523266874,493000272,604491155,829754068,713248459,921024478,262030898,866084,520289526,12790,857809,237735408,633715785,110880213,456955125,914368718,985121,207973,194566056,762726902,875730608,972517925,401900923,525226804,392789,137638817,402003,504658903,294327940,635511080,971727610,308664,881780962,911442939,862767953,238074303,706800720,828228651,853625,699576,207528,776459295,132529190,116075116,124320,543738811,116799020,217672898,822708,236910596,677700346,336428,377769422,952918764,473432410,785830539,662893166,527494485,258834031,153209976,515749706,724619805,776589498,514719571,430149090,227747538,495879839,342512208,414721,266792538,636854,520985765,352619,874079902,126703217,586131,422705691,329556096,331999162,554706,891290417,597341099,960976,312790515,456079498,875230566,457283706,424934849,776004002,797483,361900920,791469630,579380,635210130,330459649,882231372,583761093,456558132,631236034,998666570,126504655,296099487,340056169,681785864,120507,477042817,215532423,506014657,297275,628394625,162225410,502175,764376818,352335041,883464107,332171228,537796,328274353,841039056,655799,300139060,704123876,338835320,732362069,191942,231684634,745547,623265182,523460821,860055391,161379283,216654195,191328,345550259,873148,237358143,452454038,735661986,537090465,724300045,825725586,730779135,155448617,778070742,542963,387159,186901857,364378542,706455021,231515853,933524190,216857826,522457182,258754436,498516827,166821858,512921483,545609640,275385222,304149,672219112,326419191,520767181,906454063,862554942,681534463,744238762,917343255,884110808,954107447,133577724,645335176,799702497,756762718,517818,810767491,947547007,570816184,497261230,438886626,552494634,396990,992096615,173522316,683645410,894739691,959583731,223105680,934498931,524876314,808710763,243716079,748627079,400504758,549359838,649551550,392546741,555434,949950,825760375,447373136,451850937,250807010,924012578,235336,786101,917742676,850519509,220067691,171661041,518277781,659276904,800992,254726252,634692,812615,946189157,941941488,828956819,12375,898965,312469410,990596664,981770601,679265526,662856583,430231318,766415079,883451606,357427346,671465,937991,301779,276674107,434096234,631487882,265332187,650203558,781883077,835700,185249754,273998674,498963232,565139854,58748,236907120,758978621,320852,253890725,891695770,758745,799735850,441559,562078048,466405,399447055,697694,325472191,202462,453330925,260099,155525865,173615708,124423527,376271695,531564701,816912440,257773633,607947249,563656467,534388440,242219056,531084541,246843134,229746941,758394265,619429694,887390655,937521543,734338253,914289967,484943546,70870,506055127,699604830,535841,546803773,602666135,541087,879021329,359925153,328329431,933248,622476921,574313,863976,733202618,921924199,697714699,462803194,497697362,195520155,811925915,105648164,564558586,576037372,730610111,722759795,986232,726553553,206185182,590681250,858381,399212,650570107,756481356,598756,816689525,484177257,138416809,528572953,456184,458498,300499117,312642,681880598,914636321,773324182,861961,559716224,112058799,464934,707405041,249898493,129720076,111530470,420008867,694618672,590581316,735550410,867724423,971392011,706080650,163669841,611538556,953247478,633528125,151985780,51286,893446253,334713654,422452,953968992,812205285,113638227,858365624,903166536,109152871,140505866,562786742,286778508,735986174,330005328,192547544,425933027,864816,93368,104572019,267906049,946615767,906797346,622158725,101795463,562817594,199626636,487905580,540325036,402479468,982299309,378875,604441244,113276970,460511401,721181983,428304878,799530159,801458538,501466319,747328,492142168,130485912,363022954,345806221,475752040,488437376,742889847,806663775,226290576,361458946,835214296,612006995,35418,420239329,230011070,431114938,640446,524207257,560100638,344561585,744149222,183310,556109070,335758,166773150,266023515,725425228,141428121,979025644,946370,957814785,435838368,451177,664629244,937637622,938941835,534237003,926418303,119294,712197795,235717620,736679,536445643,521003100,815550424,397987058,834142,408198353,952161060,686111758,603488888,256969267,33529,893809,72145,416437029,654574,95707,526946613,557696775,840581,890846229,470165110,862735499,575584276,227241938,510944,235074,650482801,241640637,248480260,631193465,649421136,181067325,996555137,814412881,266994211,697349,532887715,446191345,659261185,326823347,948927,697950726,669856606,196264534,406257,685239101,188494918,415224958,427800368,116966,212593,135514,203490,768567382,845098699,29110,515247,392262,20056,754829102,287933,542626850,269565611,623477627,246226636,999339633,638915,436513874,235272,141109017,573477350,910280269,797281211,213579078,747102,791603211,710156,118732,954386589,32543,771351173,670121344,749570,507568,984813002,727683831,604018211,266394,685050,599652775,438044100,189552358,584806,620673592,383081,151649,326679379,952239277,241386,672684,708206546,106297004,642799721,195454350,110944065,233396,186407050,863643,580278012,197639,772726971,125467055,896639026,588790,272392066,531875,577349798,642520227,185738010,985351,338279552,217191046,227748555,890407,674944249,507740533,259992314,157244,330924735,334748380,523238836,719531959,307738495,355354903,564012331,753844743,316095600,455168945,56984,135190353,256482935,403876,585918,144815215,122754883,512342771,964262,711151180,507673651,849767,870005515,63526,304051473,510332,737689,985891,137317317,843938757,373522894,482467,910072520,746847179,871053144,577987991,167339,411045392,254274749,411707,541902524,516919864,510390155,995070680,982114042,725134009,670801749,624181537,128992,494029,383816537,171856436,481858777,845127988,737785406,559353,645169,942998879,465952845,629926826,561536,694499849,989648284,991392035,176592647,531852165,820149052,830337206,438601656,849803554,887274780,522892,351071,635001762,140544046,435582844,68822,169950286,361063838,584911809,373761792,385199666,790324013,462774014,788681976,606905790,906549,684193890,866900773,225960,109627926,986551010,153846100,681271,240364876,175239880,815778185,895369334,800518013,166401379,932115708,235368295,108686545,453264546,840367691,200145319,841526406,358815376,268629097,252255803,410052826,862370083,210416005,944297621,211085949,588039709,693617430,848285579,543329566,178170077,191851,986554753,167344415,770036,889904345,693637329,370045782,958586724,439580912,528918,869515,505879,305521,504809,646845705,770991044,750544047,311181417,363975308,605648620,101652281,741927,946925691,325860916,350429768,881324983,331867306,152332949,624402360,872687,670572981,934137937,715664,304782226,247963,410676029,977524,641730422,859162349,314718825,976222671,525931168,413535277,995582521,826053812,291001,394620,567988,975854010,246529,804050918,644643928,554005,915486537,425181,133785743,579942915,381007595,307993,397092216,413907922,332652057,399861,883839,397904068,495753,764313600,438131,594700,157814202,171319905,414728009,901334986,277788861,532193480,819853335,227782766,882967466,784348934,247656457,729218,773915756,229031863,703548727,759321764,470324,423748634,202080,601587248,832607374,942437549,497589109,789815142,639440,446356377,946302716,693600503,765290966,193878,682533355,433729753,563395891,381283,150716,271360767,693388831,774049951,337073409,647722693,555387131,495652286,264863052,318516886,300546882,601907378,179976766,506136084,414131804,812293,259128738,284547753,188257,953520589,271749427,402724745,625246633,120323562,651611345,799809072,378211037,961476978,797236,559071419,170442702,425334,185153191,281087373,430156845,923624786,583953239,891213706,941867491,568331,109378993,947269,530117991,188601173,199643740,285134392,723396756,185389484,161077254,390620182,149967,278207018,794364879,382662850,338400126,918336332,707909667,592701,77939,114573,665580155,858238,151085647,693373916,921347250,236150,238967214,385081180,811195,619584,330277384,560771,167754251,350768541,456145,766049,777975,347546527,918216683,91723,398941397,295268564,135058253,642885315,695252236,612349101,432036264,685164778,805971075,937547,917768,729197846,911911,362617665,376872905,733965662,494511939,327175592,285508465,921387986,60204,278974039,582266323,707000536,707892643,722380392,550948,735719180,834623774,854229562,310835477,995254312,721655990,319186818,603974,688572,929883315,800434295,776899482,593795496,459841,888857578,358654,601228746,383205056,537774323,174862380,810989298,715415445,286164,169574452,103749957,65027,638639513,634782301,337217408,948422948,277937520,543229258,386836779,925176140,740259461,904205162,870008388,189887033,360966808,173036217,618860481,452431992,973228541,482737,997136269,732456673,938633069,153561334,473871783,393197186,323478006,498501359,732063,407329086,219765748,559673461,328765886,364507267,450380276,159411,806486242,213071,690505428,828006019,572231541,193884728,696924,675546142,681650926,240100,411437587,521207679,131918760,423641580,107852757,171999811,657204,393577228,317066610,733757,334595294,541366303,560794960,607002945,423125255,120870850,936967779,939151,198901255,376708517,343789407,135261716,469130451,574893,412140580,402258712,937187261,771372,89508,636400210,805879650,163182,944175083,740494550,431447489,532299265,853471992,434912557,821855486,744834755,794068551,278625803,495481242,418290200,440851958,115175,993365,671379007,971615156,221348,465101343,414261466,299808289,177183005,210599241,647523970,715935064,150579753,530438612,280208402,978571079,634519730,969464288,298041057,172476449,796181744,697666099,993930928,763474,627463962,522158535,319198576,861333401,913774697,367737774,563510646,972649,825875752,181201,122162,996458,939428216,101131165,654269001,311645915,928682,643097,292422326,516758048,267699414,595626732,327256342,992684,592779372,365706020,172169402,924758822,347492038,594785,556222802,834135488,141495282,969279055,280083,586698011,152814743,486969244,932101457,332190571,624493105,24325,276604,300289345,405511662,705182980,463676684,448148694,592359223,244605390,702808,531753026,494377485,691969822,927697031,273466508,299393,179349802,304706148,618082802,446099248,685669,472873102,121993363,289246645,719659,300920091,762680,644322921,67540,285747770,57004,881658183,705605317,902180016,509497353,478792442,122779522,397457252,301034209,551523,40229,667720751,836444,454070943,866397881,926035,536434325,133441943,251909849,169792181,324777735,547273371,874000323,396931,996342479,804659305,659428017,471326298,552394264,858377,768952,997746390,429951120,677599952,117113527,444143461,862151588,643046057,476268246,402873317,859280799,208444595,240479790,665114005,771317552,642583255,126614324,215597,850769861,717864282,922701394,366719406,953823694,319173,426138205,381054617,441739514,255811862,630978636,210202270,354737588,527370680,509256059,723575292,395802,123536632,942944502,462723632,652669690,492845,615907018,601577249,921822365,527465,856349122,553436260,389614,298060674,330726641,994391485,180667529,241292273,960222004,486501217,991297760,810431,534240,499934431,403151911,923774022,866237077,196222103,265084513,986265,512034994,203771,588649422,31566,427406285,448317696,555615234,404711067,941026240,122580778,895081378,807891982,848702449,420029055,164515,939253,536562504,897893559,213551,69553,556619421,689921,336254,377828469,985866392,967189,469076,661802380,532297,395596705,130851810,843281590,881473,140725,939767418,683380,759331755,383788981,365769752,642067039,364077227,418111088,352273444,883395823,495935505,158391114,678074920,596171026,480463138,819993,574246246,274155855,699681301,210158,288341708,148805191,240609333,881785509,228626577,560653231,535467591,977442,647510949,243208,605761140,805594881,924271,866505181,742172341,486158571,661195085,132626210,222605,852328497,222891056,66996,41627,762126939,279892,963037441,956754,987769574,171651883,416721079,713423023,281581368,600438553,778494465,416272787,227072193,408121744,586342766,201226,517987359,501730130,308623094,476495769,219414086,681173127,232186212,214483888,331447791,927338,699095780,884522,995601452,464472123,157465269,386173,611291,989717078,842997222,620679086,950096940,148256,203328937,722832037,478234118,359312878,177741145,704805,325378044,208992941,202679910,426657335,153006127,358430098,428680187,513152051,858371000,683996,677752725,187991758,594391,962887810,580263178,578555637,872589637,736481538,748913489,829960315,958065728,736334001,603374330,744595989,277093467,881622690,794424730,481106394,942391051,829149880,667241967,516793463,445964,461642748,837640068,343274777,476672028,388161,667057,452840947,637108492,455761454,899531986,352135951,987281132,973267,476293,725162529,654912,484774,824651956,314318604,270840037,611318509,244340907,592654419,532343988,189245832,259862778,579690649,76053,435382,868408027,463843531,141221594,573073881,721930469,217356,408291587,273832781,438786485,846119619,523960734,173456199,469568263,109255904,643595573,596586150,230814,149644278,482403311,163402459,236743807,530167554,182156769,103615680,249350489,122384381,680505759,403920,689357622,634667747,161767862,691779332,793514987,860936912,336987,559434479,750798035,795984565,865871074,721597031,391040687,801966080,801841,516188514,729526,156250,953861053,957225389,838424,817461,404480749,892509518,460400534,589028348,201705577,217179,476127765,533701083,100253046,987794350,306466983,618274,649865592,321432428,949533364,197244472,667355,424067,589248746,918371169,724226496,842012543,613465917,797141287,188919875,781270957,723936,495348246,353070217,431546546,101614018,465171658,910445527,259499,266819657,886911997,294259,469414540,861265,512985362,437704,508960337,654662626,293691841,102643722,502427294,135214779,747142038,413891669,337010422,139465,917043556,544464336,604173,577045930,932437101,158750,294818399,523662938,552674,490892504,283001117,213551326,154873801,713029362,443440090,131586547,369665922,553026,771435,825273663,882426511,473663126,814592995,617269,589243047,185515,687745726,155540,284759881,733916274,491924984,119727,644515,962094259,420925996,786978576,866012826,450309159,230978187,446559256,395988,956244685,745190112,562952313,683083163,410843545,276323658,130315089,501534696,743541,271428637,875918951,460141586,311752528,693115,689860,521291,483413,259331994,429836023,141118977,823543216,62546,513201685,555707671,732494602,91528,626924757,215828234,970675281,983272945,317926,930585,557216326,814799357,549045249,774415,975221177,433507589,826323744,706512849,651269322,695926147,890961,739029506,722172452,466137,687041664,295337666,422071560,837413614,217738922,851802007,646012,712755617,266213113,379025166,356163058,844510726,466098382,524772823,881821,719057911,648662543,286985636,852228189,832706957,785236389,689548426,871389,904404889,841415889,509864262,707700051,914895368,731326676,386461922,372581063,904498,502777,594199,265492108,941368306,822885735,504622196,694906005,485251457,644329,885743007,719175026,692109,853197,935134769,949776830,832964715,114781259,865761042,806514575,693720570,484790,465745940,966228,732815,403396591,142095858,847969336,811963665,587680778,373936689,338654,487594052,625551408,126053903,839981917,249609760,727949594,167133827,662645576,226128,801753312,764573,105033989,807322365,477655867,838507409,378116067,631884799,745007768,828132417,444669723,356994184,778238970,929444362,651174936,510813520,148796823,280598888,943404389,345930500,352230678,322700,886725465,259644505,836743898,621964693,195353,740768280,97348,668130212,605386770,394759388,646009857,448196916,516476,151953429,456861355,247355330,559286344,536811560,882708458,138461824,576582912,265712260,305976289,684081086,774765704,831824107,360670876,775458133,596508921,143004301,164608,979838159,999996630,893453,657242562,426005995,953561490,854858290,368812,240772500,745566046,599249102,838009,679471,482752331,791027564,162682212,636858560,190445517,814660725,221517602,588392074,291323182,570298878,581535774,245998,456950415,508700531,450964,727874554,675440,283253437,216641085,867462288,803516119,970095330,966349941,52868,300182743,184967777,615752957,827994081,142919,384008157,961146969,447335,435976,603021081,81056,320522027,474709496,472810150,633780843,789260714,249944729,214708319,248200710,856667361,888033580,76410,290185881,214441877,785388639,175107680,335265445,942856861,767376602,618389,622795,235840205,402623,926695382,122430758,971577689,236059,728530024,931905861,521209975,452440,470920985,527782513,727229070,522385717,931237847,963283,364615153,832148365,360277839,876191001,569210544,788393213,277999404,470582281,149095,998281,740222675,453534846,710296858,609345478,816660849,805992176,982107086,878998360,293508726,750341045,374129588,877411241,678453,996031046,465073192,823300,220766191,52189,166115323,564295657,80323,961760452,846054444,878052943,696278642,460260475,480364517,998225620,948947,123948922,609887710,318107600,965919783,118552364,110642032,225608,800419090,383972500,814058571,555673134,882800076,865011223,975161595,770101848,813827676,870619532,644417384,421845886,161806,336467001,195388,833696,279199987,236420751,548471825,345012784,154508790,567255337,112685448,643865,464027,976939217,418397049,380081590,762599,718126482,338981043,544253852,741524348,872917201,938483736,193312171,961715413,484177453,268783214,951365360,273551516,848761953,507478243,487912089,300048750,720608471,800365950,572235325,203372,113015860,916821157,591527,231504965,196131217,257605767,485684484,329421343,668505728,582499,666412011,316129518,348174307,508858882,893522179,907418303,794742444,989905,133409848,192413,847887,476951,690440679,384270417,798671853,104856,591008,735215866,285864304,982202532,127931,429095955,413270900,535194,123624318,415206202,526223988,683034947,365176515,968983440,161243242,527940991,257431433,592474964,492831550,577037868,257350160,610194,636761089,885646,656903182,178355226,499942449,349197786,220312803,794516560,194779544,213215085,294891903,982317667,316889636,630831,566434673,611997578,216403,808544724,39877,990762887,135485633,535121518,801765458,368671,399474187,535067,292421177,435925835,909550538,913002,334680173,507565144,645235492,837203,867603,607635,727179895,364672835,150880322,427457,992534707,499260236,424446193,283360121,126074373,685844642,667968875,224457,667492832,803952352,732498730,858872442,504928556,905448919,413399723,771485224,565911333,875859135,619353662,331884120,223134576,150973976,378964866,992967577,294440933,987441371,208110274,423397526,109692012,841529619,251188383,319733991,904805427,776333868,243673308,924375586,485408061,502609257,488656506,985764523,390849306,970586724,596264,900789099,965577058,878196890,676030836,40395,519368958,517590994,857577290,971426203,520745215,546830292,330026297,295078574,795063,545252,999517412,399311799,814400730,404197551,199516,571511500,896365305,303505254,758469296,152375,114880385,572878504,897759008,454406598,160191282,476157,134745046,270400180,863366579,449400,708577736,479028167,580844864,470264275,90882,392425,993509334,882009468,262713568,618015640,598355214,500125212,942315,185705692,583151036,295941155,706161288,607248440,215556387,111019,822310162,461150492,514737930,429559055,816107316,704274253,898318111,907365531,755915629,766634918,246717604,474015725,449790,492688862,539710484,948347712,984983431,871346327,164252850,221298502,148453415,401513230,611390774,845961444,108694296,700267509,832242521,492471261,391240307,728730,626574067,784662221,642649098,570629375,992401,397787121,902570700,267920585,624400124,336975640,291354540,129743140,971838585,564915846,293660234,141004444,288325176,466564258,750678882,460020,500816,461259425,485730503,172677,446066,181461388,447626250,859776390,869379,125129229,477238369,135689557,797128572,770230737,182987175,967636698,618851,599921,254780317,645923433,395367,374501566,157350784,683670,179837589,378478,738379198,762278067,810016800,834086638,888938586,56378,827249,426595192,767511544,752705821,716114999,646165585,334528103,277830921,46498,623240216,350380383,472946,444263247,625965239,539423,153309225,821401501,839190682,167221041,258685,183728874,438367374,70852,12869,107015,380361164,165643962,374967102,903093834,248141717,426170574,228292,645739798,365427282,112501,868472,899199886,447576,435459542,689302981,270712832,520857,805743393,877166,926643,123806983,119084250,477781160,982863611,676975571,697855645,766627535,145049,482803,941408007,859094131,478938656,202645792,956599127,936961,436988,344621989,775952193,120854242,534118607,905425174,410671953,356881902,221950,850219776,167098,391384775,406358,640663425,535999074,201549783,541793022,974323005,14654,648216665,187192978,697777411,903465378,441763427,833457242,151034504,198491555,197910276,292252225,499184521,999220743,580034386,289082,165944998,914894570,685587374,619345903,715940619,555214729,129092200,193350,428177233,669387449,564274041,182906418,167661329,408528654,943560170,429566907,689625,825051202,293331461,487782537,516077187,824569588,641216,118852412,431596660,918808066,656851180,791901166,534316575,219020378,773756866,602595851,319510991,856044326,444713470,292495089,660784399,87168,158621893,199643,958167,574399,412003,577662,822778776,856453,936748557,425891733,825280322,915520803,860421899,383277,700474088,561401,975464,148894354,223139,644273,904861,650866848,120268937,889306157,842958010,524392969,202087720,636271022,709801140,671741221,878934537,928598026,462116069,807320242,410920968,111982183,108825150,570294886,799804080,353492486,604039028,307315384,367238,948597703,673973070,202553582,785438954,348331151,133426389,140165486,524955290,224204865,752134749,314707,454936459,897036859,741359898,111227090,465671297,902970663,907222,301822120,271378078,111321,685630720,486667930,109275492,724361137,978315633,606937889,838657199,995049,966352066,80908,502782588,416611280,871339633,335263,361998670,828343,504623666,217649274,698581672,177213994,939106,647959465,238772,413526674,500965570,237468,984834999,161501046,348211,126938571,682508544,586496429,891560948,418712,223443726,561191091,324628176,646681384,953429,521983,176377907,106487560,903090848,653385290,703286516,456222,818930325,950486711,291565527,234922696,229479469,432121519,824162487,558873025,649714972,638486878,824908,604127131,115454,793197070,252970217,443795509,206657486,134904,66956,297455586,722318901,285418033,845271,162712286,521686923,526592972,782953037,993604010,935916,686457584,271434529,221031074,865168934,963867380,430005945,822220554,757000130,938236795,154539897,371453806,457797476,834585355,335755644,490756103,838366776,988251207,356155054,122326116,890694,331965661,306077837,545169972,856801983,888317675,635481050,741902624,892226358,916864357,906524540,584626,601387259,336096292,888706915,242363968,681328555,280512222,304354381,142408458,295382933,55446,126974609,437551283,669920249,662790804,603254189,317968299,416063581,176077,940816928,219404163,667939443,692734414,246135486,397467994,966070917,169175307,322286663,229532036,959977,209231,424123852,127240891,867110925,632665383,510480044,970012191,934633,199476812,811835967,812157354,124091697,543961124,214628589,407267585,236535076,351475,758241,104831,978054259,694709711,923307373,866982980,973805567,623007668,362996,791609495,740289,698695368,874871,359064186,201476089,491429942,978189349,378300,777633156,182688017,909212401,785017842,367857960,40162,566111,348036393,845502821,165758011,743900,428568848,236539,967310834,249139610,405557251,594495,783846019,554977,208943230,633071818,195950,509080120,117243186,338261618,539157144,813874513,216531340,376773434,336956489,517334610,949873,404730899,518718486,335377037,492692735,704837124,776603428,343957104,601433382,118703428,185558144,452456,974755382,360076938,679517899,640822104,457647,674554299,453703056,830003956,713939,846065678,310976961,694720959,589664582,103864961,152565650,162247304,888315117,780724,198635829,202038752,851918718,947526791,204660528,509241200,773731481,509025315,975392627,604703898,583419,851920551,844538179,569760407,154551203,520480694,339443449,207787537,279225094,135585,817382925,467408101,164084750,467968113,623068030,909499365,454113514,783808219,545070,589442537,578892987,801395931,232193629,317475897,771922274,570955911,429186040,166622300,447072973,440323712,543731275,270331913,938814127,100593514,729148588,145131355,919773,717020157,745427464,440823361,890191404,113611722,399345965,569761963,440625688,312228813,121266655,316688482,61903,685086617,372484418,541227821,625256371,185482361,555052648,580439596,506584142,872685799,340201750,957452633,137181598,992343967,647401131,714568,431418201,861092956,337921,721628,719229,888128603,820823742,846132720,501968923,832176598,948634624,626324970,579948,277476756,405234,470133,861956216,849360247,300415917,200005558,203206,241338327,151117900,169849380,377427558,211416971,301534,513510511,992729870,813603954,243018,684740940,704625986,263430815,493684502,954931166,544922024,377954263,871752,764686358,636739506,239570943,772721,148863433,366588021,491835028,326775258,371091049,250737391,792720367,851353,461204534,374922230,442440087,57519,848084998,505485569,543270102,829180055,962573538,373457310,424527211,726257420,636928315,387399485,527415528,431420989,247592798,270249527,547382,362314212,104914794,623371391,174463664,158356,956256391,425297158,151296489,926520297,542375329,934668,809052606,335799666,191001,375107737,436371979,130559899,851682146,956113,221649423,814893227,986526809,909570675,744048822,183765286,427705765,907928702,65913,319547454,231724,109779133,156679875,677280882,990203180,843259320,691139812,159065550,533011995,611924576,16550,257906385,359371862,311037263,851579170,373953145,479708958,476333744,743267698,811573,652238762,130656272,108042277,467603096,494704,668187044,649984567,992517754,205060733,543582835,713439,955973548,814224740,891447606,230185649,772771,569185679,874957,598287893,167746578,170021959,331999074,633526483,374520,415545,380611,632617391,224671688,406320545,215981,723526344,662958438,335018163,338719288,589724224,826124901,994513424,283501709,805029,251882949,121660288,208940,186562595,592304906,298437556,780297723,162207217,521069454,415365640,884718,725207063,767721911,211891051,985751368,618399799,559147614,145864426,455443,295004903,869478390,941903310,371871188,841255665,693561716,630010606,180194657,453917587,127786352,986730736,598532544,601359143,399957444,106996694,157373374,980044552,200837,246960008,545136416,577576,308699336,924790216,772831759,651576679,743230503,285428581,494299758,730170303,232948177,680750603,798499270,722057005,869784,190850,415736268,991119230,105715383,738176980,249733201,611034607,358227023,516371269,933771267,201553,220148952,492079,144962,383179313,136663290,587314283,853346318,940662738,548408885,616296764,736118,639573009,262526985,319200526,353491925,943572572,600438033,555604,898168183,938747974,796697336,641068274,261717024,560789861,411575410,302668421,921548354,932856,745356527,536062945,237860556,673417424,799691,921795277,794619,230968223,381854,143748916,653347,617296492,519603846,818165872,660051476,349162586,871853543,102161952,762790149,287360710,146789014,236728693,818519227,129455154,997887361,432417038,581719496,482045567,105812157,116122,681433721,67523,874674644,652270800,291542290,587707603,752357280,135663127,966755449,161596517,540336530,713221651,454201739,608512200,443284250,629809162,490201763,675145117,968287400,570659656,800182,539172922,606351057,675411,257945347,621313878,122764566,790143762,902019509,827537732,329402,751271345,46552,356915854,832226440,280009,974566408,403951292,105743,822787866,890354,345738,913399878,605271245,627720540,499365554,769830254,249174827,359893736,929140,473407892,911862156,377888000,202609517,637967707,628891127,734151692,847651203,145922081,174558873,789092385,222940030,201641445,750710374,326211845,874616511,403866378,308949145,987175070,401036918,196429936,739351128,871229602,893363026,704284,641899744,227486897,140976538,259671484,697474498,311784952,110287577,386787236,967219875,468562327,462833591,196234181,130826237,382446,909860092,152004,219911711,306629,559508543,453788470,660333,691497662,794622858,302407108,164396146,211106545,527618751,637666400,647936269,542694,633667297,601010,334916985,127892789,393587772,855013325,412851340,224293744,893005603,454422511,617898476,169531238,139687693,227207123,260005293,647294244,295780,797619056,937967802,509752,448653125,618929,442458040,319257551,247875682,754920408,593484983,643112367,622826799,507003438,208389001,595353638,188552026,718795885,919534003,880626963,202926365,419020,672710941,979158918,827662868,78800,556147113,816138228,846802402,775363202,771319466,80864,744665264,178153288,624551629,443557197,411390204,411666,788627935,860286324,851746099,928492584,382806097,792619,530272,528760612,156727,283873625,151856699,339516439,642979143,628679364,941634,617579860,797434467,955512429,340125782,256913,708323060,970081032,821136382,825418,683484168,507926,767488101,684901558,859836933,749549857,311499,420631,943278936,973363811,968876054,697191337,479755270,967820039,960048990,810147210,824437843,481891620,516006017,732563606,886744627,418645145,592445938,924406293,238548535,221385215,234115759,676920305,527065149,922348,444263343,395417287,100131692,837392643,285485,579286561,792182921,281432019,581549836,218524753,404614822,473199529,396445,497211,471649,565649259,821037567,823148923,199733,351108565,857735,412708827,575676105,934452750,445595425,509124,167722616,505820288,359005391,544904409,416432098,579891,841757,838893087,886727317,797207163,415765404,326634224,633632,175901207,867339,90098,948359217,149548590,968825683,791650588,308667222,595208049,839308021,895982587,685314919,534187750,685278700,200571625,910157640,856522,185437,244248,146749590,992536967,796901987,645438,669850824,462624,394057357,149534133,149966614,658467541,882286871,199111433,642246534,483325,545699,723591657,871499618,457354752,246563,820581881,683155607,956103,364189,330254,950363973,512962,876676857,204065508,493877476,832446330,243630,443982277,117741,706270553,373924350,665351672,293002141,635348,710771763,832806712,577288470,748257749,261163,966388128,735589056,109831412,587444256,408594014,734542147,697968095,276591322,937455764,530059141,710839,368388543,265707229,760688742,445282325,657567373,590870717,278943343,194291730,380786964,133882806,173257438,938279283,848439184,622034,744420659,195225,871324228,717501315,247817389,585105796,475968167,499564148,200039949,830188986,997951835,349994041,755461483,150527305,684330034,133103732,858897,162215,398841549,864345981,686513564,188589531,443343,470646749,373383,852843910,304252268,387033086,806182840,720672378,938564537,820199603,447253042,729976464,267480,244236843,829786098,243883315,162453398,644899357,941363110,574870780,577962661,487983,274517693,792627231,182175123,159367731,543614878,730158448,808249027,222913,360589,187628,556229159,820476936,923334190,818274923,956244331,742599,558511512,963351598,911122185,459933,852303,975030804,321211749,849868128,925324450,879290527,102164,465242360,818363884,268410133,252365140,353213853,311907197,892284189,409695034,592883933,857885990,990486399,268783,228836,361121460,625650,176979441,726132769,876449892,257876607,284215746,671598,847633008,16506,505448,855156652,673742,845484101,221975890,850704699,758376,466004,104227477,894898965,390589,872902584,563857368,430637,918266,535287057,770517746,484318681,206327,749869470,398692383,928379754,989024684,404093503,946910689,956987486,952399446,202824074,734102132,679336815,252146208,416716605,141849083,352344103,862204,360635807,551352496,700761002,972509197,198978297,67895,370550415,358091219,769241660,155283933,521523,104552122,502340462,471064399,957637,889016793,509261741,557533,393151738,850446310,19244,357563,178396739,697873573,433343496,858627530,334746,297611679,452202216,76086,970768114,858659057,859522203,264217372,509137,413328,694060703,667848297,683828117,104031,292309226,994831340,948603362,636422568,617206028,331734053,674428,658455294,169450286,599894361,422382921,511666409,814249321,825455,805248801,617084,549557463,506910,918863413,699510422,412718,598342448,652920995,387251971,534751,344279,244189086,841750290,323950244,435609803,145206185,619501273,261545085,693671,835790644,104166389,886577932,978788332,30391,977514836,325817540,583225903,266462992,455367,753035947,294555422,716984268,860954952,463544452,914880308,869874125,883166208,814327696,580234,872412788,323745336,325402,639927768,656479215,474346004,442729874,818806631,413477783,455239894,218296007,803424188,455231977,904558573,927332,670896745,634944,785562163,767678132,805157521,444192362,671497456,515784,172467235,826170464,103670,837556440,916474682,450575824,576807,876638997,545480,919611634,424719692,708109,422391407,832125320,433360318,464512045,158818,759475136,910275372,298052031,374392337,796468844,927677677,687055338,269639,672891399,854267802,327241488,912811,544111,941724302,167278012,423606300,999890,913509820,176089483,768612452,329953675,649342,862524986,900052975,665387414,477614031,237778935,986682021,148818778,547275890,599999050,232814572,702137120,923372241,545391151,496225876,839519,510881288,618231894,383049398,946651679,457944133,553959597,733490,560456218,219644754,121273289,362010,742067751,109812710,404796,630483807,823755889,961434,785948,282703107,354272576,810705597,320204378,51719,321087912,934301540,869942511,433256,935024329,441394,240312,880494640,799945822,261872503,620272829,295994066,767023919,108213917,807431922,489250252,532332925,522025362,745083,579720,354821643,775722,738141500,879894495,879071589,568111,478234,415600523,789271317,697652156,350746152,244885756,341148873,936541978,853380,167026979,977548829,669759042,673647293,959265612,614093,274929433,758287376,283702213,727003837,70129,340663552,941574631,913550,553544882,907555307,176655070,100437,764260258,298171308,559105018,202429322,522179,899056833,936816,780117367,617028071,271491539,425143324,715357408,384000599,455453230,905826010,557168730,960097026,227246741,501263563,153202,603258038,461809899,687115466,494943025,849762,278703784,389138969,975363385,828472444,912216,80738,493305042,318618180,111101214,452735170,86664,968796252,386742937,259935743,899475,291256,647679,991810547,222912422,263149828,938260463,20863,815581648,853111669,122187804,640594362,428280607,886936766,881953771,216877,579930,592895502,951605789,56841,787784319,826959325,765856632,879646466,45877,904869782,475776535,840256555,701596356,210616603,292140553,560560194,903174690,242236842,252951714,909194363,722042552,628522,331374651,446650597,152680392,129384488,690965,742607703,738289115,527932,214546810,234096086,54082,101167664,214176511,712651880,762343688,628517581,266280,118636091,707311579,935471995,301515,556166174,364297454,343863491,575390802,839027,879082,293227169,956985712,439705599,392198542,228773861,617425,325285693,528690458,104635326,287633087,273413074,540765118,515931075,737081637,68643,353478677,842955213,934847539,923266663,814183356,693307,752375,211396,276011314,991373167,524160,464606,176693295,341158156,308598451,171164645,936931585,155151870,735344292,563435549,623102571,831300446,927376417,988720057,428446881,674916092,542658853,697926,755875839,544864205,162871606,802470,614367072,176552838,509172411,197541334,949097709,671932616,788800040,472293231,556426964,657540662,696554609,968193469,890239508,158887478,680943133,895905545,642306979,750167,763379074,201193702,804331,229222890,969206574,814029005,917729182,258695142,514472133,869333591,550163193,949800669,442780851,846879099,101418323,110156368,974224,397142,443539003,112514215,311204183,421476393,666110,586429036,457945728,953985846,903897696,74664,700730235,852854158,470614766,733538180,957999127,20992,477800280,300709150,646781427,724348385,354754,546814,813156128,666693174,883496796,156609034,842991510,225344282,694594568,883835764,112012937,406122424,502044907,348880,133124123,327646838,127318038,340921570,919764780,340812823,208511634,786922271,182648207,262316044,763457,591261658,423315352,520660226,442750436,958324269,300901174,782876,995536675,153246116,537950925,617362400,616768,659633911,320437213,390670,639059004,759912786,661970381,850320511,670188250,199102159,510437463,514011,745353,388375,606657079,362496,531449,362595245,434481,594371129,397936305,735988,788463653,221405275,940950440,900125642,832256975,534628088,418201062,178557,916422,50640,798510268,488967322,404148126,800286244,391952987,868987469,261935444,879224971,567985337,809554127,917651,318929814,422676998,368384495,854153138,363323,643504628,486032986,893713247,667531465,816277260,844462800,370054618,150665,876271778,640103640,931329321,282137385,293293,234034320,819891799,693584,275295,390962368,981145,982109837,993316780,995668152,764632783,591713324,869289769,903346438,935826381,228315289,506275917,672653415,243729355,748934430,480239220,856481077,263669867,344620829,658314335,311307661,417986217,841598946,644950852,786362891,393187,372357650,515183,645464195,67982,339440057,321436573,266163724,583942832,224713381,707665303,767954757,650460041,128177959,435396822,873406282,464573666,496629841,290538869,855843,529902947,156521536,980620967,203832220,644915214,316229501,15493,870590839,997995536,614244119,702877340,490021888,817664154,149426320,92103,225011,332233040,384004110,234303225,574224,519000101,994040,31756,515885093,411372,420337499,970809927,838513260,221208047,485081247,213298771,434328,281262,80362,766751390,592438641,351279690,763021914,901111105,220534781,655671,164984650,344648546,729757818,897052326,921343653,966432406,753131220,190290977,420069,978910704,517534846,549244707,891245030,555320445,640925,950488693,655548217,152625935,941236017,882283,818135242,309192,269119800,277648653,959702270,102120093,581202501,545245975,98005,342922422,349938957,538890352,164224458,521655,601600243,894038385,677234982,755313,592156858,957223229,653866179,814666,875560459,561795289,668393472,408717305,242262146,603536010,893106,757413827,454444,52588,306867,236348420,503948590,579874535,506125463,753595910,207728291,952597638,920807754,975203368,925181664,189082457,235277483,398617779,161864689,370312625,164447,112030279,499011579,877280226,626975505,389502961,477654141,316324142,931251378,176391289,374763153,419709077,130641211,811172628,487337683,483380633,420284,371827778,721205951,671532888,701389392,170661587,602075781,691486782,81614,474772587,842413690,511411,194772169,311548662,822343016,313049906,866616246,481295665,457053895,980433408,767428,794786581,138587360,736329961,485340981,153734880,189358305,269970007,714859334,955600468,190532657,974786730,836146172,468146922,826437929,15060,149988198,301361415,584084373,285237,461223,547597138,818342656,805870,238984782,849826589,506552847,298031498,526769,255981996,663512557,131815332,266321515,458122133,458306995,802775343,518996633,253625134,824132019,932249820,101705700,533200771,645422169,856704406,295407052,210718356,323877991,406047225,398842430,581413,753748,704423227,829855,669428585,733941013,690199548,159979567,401143676,634753287,773639940,527542179,402525,483682,171744669,564194,739121124,744489,418441667,487848207,299272538,825339842,890540814,364692096,224784503,924258619,918202,377222805,372617,998396,872544905,807586924,542946,906644450,547889115,834492,146726,381337722,362078453,763109822,703577985,515979330,856708229,964605562,192483992,565996,46281,224112582,858985,229257024,203855,296929261,579876443,754565,959672644,376607,671216915,33568,493494,111808115,421069338,510370184,818436359,108087347,760877499,262350362,739879,723015,217823,749715,194289342,279789745,400994259,478173422,354426004,534247878,794466889,383218019,828934913,743784155,375908268,443387908,293565213,636298739,334828625,794120273,857073532,807335356,149252235,267227074,309454973,988089886,812232,387406430,787566505,686151,259326171,609619659,410719612,909104214,882540048,683755,872877641,510002,179395855,971508308,502794,307151,134233262,161360746,982043,795773444,413967420,770559,925229413,144462304,585351127,813874907,774467569,455963168,552998433,254090738,568033626,829128462,270626911,164609544,263425930,582961900,826964014,181926936,802972,913470543,503875542,856816192,764162,644289416,206402942,166912943,940423216,597913992,171499164,357661,863245102,138834,208271011,851268,464765,622609543,846019133,587369876,850040332,205353,498132565,73681,210105037,569581228,346603722,543418619,257449,736849,674719,400894210,115302448,855112,733013075,741986,733317446,949692,692238151,231666386,34627,300427305,483671,244105638,485692,187151230,201025,582356506,747880044,317540122,804021411,964416716,719824478,871675136,265756678,172771657,90886,385324724,362536469,639919825,509190,594640770,444085846,662224442,976271910,514207752,319981261,372625988,753613144,701025149,996368826,925492311,524670392,668428,867116099,317459,323169093,42227,758305021,269877880,669697374,794638,221224166,814722,174846253,896141544,46958,850050702,415912549,816025900,793893181,91207,818138950,523534638,12530,895197961,701275871,657353629,663910724,521902776,977978,902135114,426441,479448594,977111,808285051,730287553,337726579,434827758,923858283,18435,653047350,130463771,711050265,548764,654817521,603021,736982275,263448,596821676,865026135,862657,368589113,474955,135405810,344613675,533640687,379646476,252408404,130171135,924494645,895874234,509325474,424873436,647157,642916280,533434358,345646393,553463526,154392266,856982945,733600444,951213680,956634813,482085211,515468452,883379045,758083471,669656168,382062942,201167,314598,465637083,693629629,630727784,189991373,900435626,735256587,424902667,408334619,549620,150047303,797671,751031067,670924,673320932,528782,407023643,787646,159957281,631735,883062,789710402,811180323,475285399,604776631,777894,744160226,894848726,350049,51244,973862659,170906,250081425,777204092,914720261,701598329,256884,427020,600414,234869417,166965,563160029,425941727,669813768,652721,504392034,811067,322573,224922408,205676864,935270895,658485363,191750161,413912966,615081746,605299476,864368054,746189,929655233,440172117,702608892,967185016,332129316,740174926,419855627,844614336,330460608,667039378,813786955,804309,335748947,663641,290134442,682279016,594279718,171419836,521105122,160732016,359646,536968139,96283,552946449,863546058,61199,175755781,567027,548421571,770005,498481864,834929033,97587,338243436,368173902,791694016,798277,452068945,147586149,908154638,785875,992415688,597517960,445019617,519950375,513781,627146133,696242616,627691988,151294,417381704,635020443,818621280,701172,776799,859473,598967760,504040796,239837452,485877351,642461658,562615214,981382,74236,751912093,274816292,992857898,889181,493320,640082,752421949,695864461,984221406,752162621,136948038,751870608,841607384,167989963,275019,516345418,948548274,542473818,424082624,584982,279946,334773199,460438578,938320727,643273447,729491850,195287733,706809553,189503714,442842910,386194769,878249144,509044414,751271635,725347907,703870328,940989283,127101408,390204,544501649,567626707,751459287,577577148,801741838,269087427,473584472,505689303,685432,622274515,300344941,664985140,338720069,801275065,940262,226623025,610967859,207059727,120570,204642885,346724186,470422399,972523995,424001,924964108,255067196,400180134,543154623,359035252,111693365,30610,393513013,739429301,626397175,607266577,576828050,127364722,396691434,898449,948397,189376111,549864539,889894401,105162492,700816277,666484,864832443,191612,74687,579064,398571110,845185242,336509576,925865955,757846487,526756248,899870114,647901744,401847001,105765064,987650098,679425930,545007,822010,790502025,621258980,651236,377720847,757765721,790826438,155640135,720950626,465747519,232203061,379160319,782185970,231543989,926519,465376014,193669,171568740,541923569,469507097,482675021,633270046,23770,470928811,607568285,363167541,698497,283410416,851206523,215867138,164317274,721200733,773394572,150260,852894286,779016602,240473234,129939232,311924502,318996629,331224057,603441941,569127567,152126412,525038410,292081585,392894775,715381783,576558883,172924671,947007128,309473964,839558792,778079931,666353760,525684624,357211891,992969,182206311,939820,293213,234398506,143561366,988111350,620656797,526768828,120684694,323416693,169372599,970769,771062509,117496345,617543461,834348972,894132183,305605851,802506,599796469,739658422,83432,725760711,186387866,870785031,508057911,187714348,884523280,745642,538411,185661431,60785,830469271,435397,898591702,855450207,731915046,554821517,899484917,711965195,801248739,981163031,117667,400014933,146860569,483656752,169729082,508788914,802927670,241433573,724202466,986100696,320698486,269196152,769035739,878504531,195394137,751272628,275635039,980720635,183259179,794068280,32215,968076365,219630360,429310585,983180682,991896256,790810757,653051408,801929934,736148391,741617089,557226322,343424120,233081,928388750,467583566,185034696,815370,457297786,111097679,855214203,840208245,768392995,664979757,187531148,733525485,946360036,547515892,806185805,190583608,544374,887532147,217545873,910321597,933643687,741567907,275773280,410209918,377579603,387949907,323793138,682052023,297733384,968270790,533249732,876585544,329087903,774434418,349058726,658279,314632394,988620994,517100,288086965,321959,471263,344767677,770783649,865912,804597881,283486113,526997,27858,175859701,503704600,494690002,497163,615598618,490264,112679323,845948645,203560178,997114,819415083,537723,716099317,944270,325917200,852687753,665501989,189907341,620119640,388477828,891895335,312213208,596062180,655578052,662902596,748452,912753326,643497701,897929831,188179763,555844773,609819033,702751,940862678,152520,719434,59113,331997055,422395,928941449,140164617,999233290,609829994,239227521,14914,901647313,846875532,612198,540807948,290286863,426774128,946206160,690749537,268565045,416486,211610239,321232002,336632,131725566,402829,361462783,927888966,576193424,817354343,364404060,627915803,568108497,892661,153489909,499478915,157178566,223260,861999,791283311,985107452,249163315,110575445,642969726,775350,591080202,993105912,539727589,410357,787363827,596256,105010334,231931,813471805,849563907,705977670,591144194,637780774,175590999,454459,134525,725181681,218270734,534470586,635262915,140601,350672943,867265792,283080939,376162926,329058621,293267906,463108979,247861610,762957702,201120342,471375,541730585,992702199,12714,898140384,674668183,492182608,695837899,834407327,858543277,330910307,929413,457469257,957836316,465981838,305927541,118814472,535414212,438613706,807400743,107249687,704678883,609326106,589481110,557021276,693191068,971849,277159883,492585303,225544634,141723888,902325725,908052299,800070264,563326503,643672607,954935,809971693,870086479,98291,358524491,992333,724120961,473839239,494420839,692501,845824030,370304022,519220469,599406608,670802178,806103518,342728080,783463032,15410,226238862,430728451,215573843,194181689,409898222,155338023,245962457,652975772,28823,229848849,839473765,953297931,856630458,434147130,749790,727297281,104631634,980644,506225040,998182478,402216044,891123775,375020080,183799411,224013540,192974530,708603,483018119,550114133,547823646,493390907,715728216,463308774,386399716,670445,331432,720649187,284847265,830271958,448521587,754777480,781390334,627324578,521068217,639233870,752972380,195608062,333970,108991093,996414,947646187,937048,308801215,612752851,700939416,879633810,371455249,318727794,412121049,162512209,738431077,579926814,774500529,906501318,181684127,501478636,374361085,254711819,891984241,255378090,619044098,532317099,954599496,779401116,578712,425698022,685610232,717066462,498250916,928667290,516194699,387813622,681126,123470199,733494288,582497593,768631278,638953316,921506791,111334907,166360319,580307,596899374,618305234,997406482,515539638,563568500,294223,927641,904652090,662913938,571886186,656450613,244689954,383159540,755604349,821301599,279435846,141780925,316478094,675778744,338369248,950780154,236199,380347,145113316,316656661,646710769,151467261,728637743,989279661,912947816,459864888,846475,378702826,206515962,677496464,930096482,572775444,379547028,114598,334579764,244428985,961890148,804395056,117834673,893929349,614855,544107772,64154,682654535,988047136,165333691,810326905,706227565,246820138,951110164,912903771,353594787,836597678,989172322,303981553,471238465,727769804,486208537,488296,872447721,397088734,292885130,97928,242297931,552911205,423997298,559578440,595601748,558836,541122861,742715853,393636996,144321080,890191908,338210225,607437048,562082349,819094776,709632025,636372580,203803922,494188,436447,565607,975320269,324899,619367993,914487015,229272821,796489,627445154,849698798,423258663,503911980,282205208,776080,395944638,807793616,306473504,616925969,754944972,282840005,491428879,474418312,892511558,301317856,335893674,843381348,980435306,681538387,326641529,672422505,568892953,179902490,724202951,891490,647928184,340152330,704538849,489337,821774,880385052,350929786,365499650,339543087,154663414,906799708,329873,389381397,650105496,885942,911477360,397782,809772080,723908360,846357,423866,993472,118623,647934534,205818072,730900275,439392410,500960093,758894,920577808,799494,166736803,389786077,319518803,349278996,743349131,834388701,746585664,762806210,221168207,332463007,728748625,495475584,541040,899068,603042421,987821228,341244057,955781467,960326101,137516143,963278018,778153897,843948400,356055075,295473,792688213,511098456,760465,601051,953673745,219438939,968056,199468768,973464691,360644397,611574104,537886,986799057,400828656,110620,85601,214262067,600433029,19086,500532943,577587351,278410205,701328262,521601165,803749109,441246157,566096,927818294,310519354,712864876,746822559,569649,127948,382169427,280308077,509815458,176358974,509111690,700502,869076897,467726411,538123939,712406834,156965054,649775707,284967392,895406525,324371716,553526004,785635116,943877297,587205146,990826,345531986,356994633,932537792,738287701,653862830,799280580,682322,227734736,387989168,994487639,922185,575417422,790195484,212535288,529367200,627456653,28305,267432908,983520427,555890830,826566590,479826451,515163041,864834526,897477692,492020687,873763271,289007284,162107868,958846454,223812644,156572691,905975798,709989,914354843,665556003,797258199,551300,841165679,366878759,282173118,781044,335229813,288118846,737378202,181730786,378809298,703798761,166566227,309063455,250232438,610599443,333094373,801360310,269624326,316082617,109123117,756396252,979339591,440546928,70135,709325362,650395905,102639,547511852,129296186,320738,998184434,216532547,840482,392507,250941812,873884003,879895995,413396484,975350616,727699532,633340667,633912,727386926,944890333,589528,431652252,708299954,250266259,255348,828655653,666277980,645057633,320690687,894659318,823492467,921457433,845565137,532645867,312647037,607862560,475267,347411828,979286417,960466,893677321,972552092,158259323,554043943,720821743,377686158,909887144,584821777,111190793,194258085,52059,314677760,748254161,869140649,749404790,376638,632607374,514411092,130848119,370786447,767139,159689937,457583,984556562,368690931,862113215,888747898,198279087,745461722,606579974,228796,338517490,449212930,704846815,221311523,196518091,905406362,539160933,259283679,282185339,501226303,718306397,750824894,273289,145992700,75839,812044,183743464,403518572,380196803,547518716,401579775,692137612,954856810,664839891,656622,62649,236734,764104599,682260,205678246,158193,338018182,403468515,595397828,190187567,968916200,541640812,355099488,786890845,718430,307520409,349671,180858,412640006,504660974,543915536,264953104,455970,689405498,366871888,702578689,742126772,143712487,238489,727356063,118040069,143688838,839223072,540173399,625367,146109318,213674583,287661857,862328,671588,335164059,777791493,684891064,681242850,859866646,961899,287446670,996589830,232907276,983965907,945638630,535307307,683925079,750852,555398,461465777,856711,293800,923945093,603045392,130945739,825263,130303757,183255095,421447027,935000,353298018,123327759,688842934,511052964,666040820,367140440,320678102,573228060,613364236,425684738,494762284,697451,330767757,939243538,696542315,205814355,192142169,962661612,134057433,406651497,714283,179726536,295524401,399539331,137007571,221678783,814600829,249680,189283067,159741811,222461948,416677350,960638729,702233380,656075587,195499051,733178792,463445728,158301402,633380814,584303463,887850222,426772704,466126455,357890858,119361,210712765,762680047,802860,843303629,530527850,814574168,224998,250595301,957363730,871596044,615316745,412796589,361659,344549529,271932618,323661375,771291403,201758408,854978462,322907284,147800,900870936,915295650,662793954,449036100,215605242,680825137,183348799,143362676,959273186,320712396,547800734,147687912,791268643,531880,890719725,22550,740203276,451655776,861453883,974166759,767205373,657466,165870739,736132,954561906,690097460,256026,469943151,479509252,921560071,444439478,540871053,838865,723196359,915252805,404078113,736776840,129873292,743090,904906042,542196,795135802,756327157,166402,260678,505874598,277881983,445023,100215402,191783769,434515732,642495289,372181627,347548241,585943071,355042564,642539454,613371147,601971393,855426,625936,808095426,795995778,697268523,705724044,641664557,311866,145606687,992073171,305407261,941188241,149102072,222993,450993020,872201,556954565,657187148,594577,314387673,546728180,133121000,213830115,447185817,117633592,558335262,654865652,905722447,251395,211635515,876792,486837,742618168,759822562,988007,497154976,493596147,692647119,847219282,695447111,475849637,108100176,422591408,915812,721720665,737504957,638648040,790943,758343,396960666,876171659,933001023,962189473,378618957,258335752,215770171,775135815,588535,889476263,747026211,243652221,889156603,154861543,223607624,308989377,435807299,443589244,260450318,945276234,344598,637152599,202032468,358406942,853452957,828279,791184499,615817,684648,122385469,833021828,800339870,160113565,623390,395231353,444736077,19829,457459584,468648652,268668187,742768941,323918349,812661783,918581,692881945,978515521,756685695,774440527,735166,955422146,176056,519385783,743970598,792591,582312462,672851029,778687,918862132,389731035,504119165,352754804,346102,998442111,241867704,794822162,346648,441593146,196957565,48599,698578142,886128938,886186284,735645059,296402699,283826,995741908,536384069,926205747,882038945,573311931,148856748,665485,938305385,694589837,353826880,230501155,182936836,129752,835522,341569658,556465706,116187349,309948,573657,799139541,513942666,928904421,174213468,145381104,822907608,575938989,643758277,381736468,373480310,232756209,250550805,681899794,256768111,828674994,730017,193549740,402325750,814517885,300076383,397355208,995864,376786,427504816,265038555,202148718,944627497,334490466,632743531,811197,443354698,783421871,105100,587814032,298977730,642206377,503667,239858817,489210018,312093869,462802657,351964,961280000,716299194,352611238,763011154,658439285,514292904,242008503,308274,756520117,85968,746321978,712292669,338733652,961582260,980876181,321812,599878,375207,695728925,744778,761770,157961754,261425077,354861,165697037,814407939,778231697,336029020,863925508,427174882,168145097,824350,867595793,483063985,962876,674747396,254233041,545040683,290972543,851502822,304279489,337668028,122540819,903661402,787106572,789490907,623785948,587312406,777413832,983478476,772875,953975301,807864774,258388365,267787701,900393441,525810,928806,203478412,175452709,159166,156437348,203859674,203559526,460508229,126736,659496,45584,616292640,889447226,912793602,982654582,196472396,434162,535074695,607338217,565788983,681523664,341111933,534268358,701478123,238949541,216323,642260713,305262820,781642751,133995403,185156485,433092255,778069,19410,28197,974358420,796510086,578483952,820168700,410344774,558871768,179254828,185900010,343457,847992739,337810148,607026267,102117510,806021,188591,716558131,951312858,344334996,658794847,491119802,288110842,773975287,344388013,974210519,207486873,501982727,353807550,997386410,429649630,485916740,842594324,719231902,213674825,889871969,783923340,140011504,854619127,546823949,978081538,675465858,113155,329671569,853224869,910859626,571633522,957444426,190157,624085920,224865425,107662302,704075,586703359,863938945,306957423,810550693,897339413,746181111,433009,333349544,173775767,533339815,430692717,835734481,947175373,366997836,790203088,390812892,567589243,210393191,580400317,879667662,449478396,157154342,387258811,905783643,950743659,230805887,963977509,571226318,340425185,486320266,385704751,638197,363034213,785904977,913347694,334393901,58751,746323902,360340825,198809665,274023528,445597,110905238,716825122,136900186,323685588,807777620,503555193,950717586,743614432,472623,658011,517269,243275601,630633845,137802,358534126,503747412,965036508,175132,208993,226490483,295690726,963244,275581878,407731128,392005418,891911871,564753,378688,596212302,755690746,589800215,897758847,380885197,790419,396056735,574811790,704829615,606240536,167329398,238204613,667603396,198709776,538242035,441545939,557253883,310701532,106459057,502517567,100529419,313788341,602412675,848556555,126532063,100212938,902032896,277086505,391135847,562932366,927690569,462893902,839990,250598496,593993427,930528406,441178,893350907,707315303,495695778,675810,109037,212979888,593495,859558770,178284960,690172793,469344742,854912884,555846,741446632,745132,925491,227998,253107700,853579,459706683,478982,824570578,335120377,705240515,755786407,234843,469388066,511304878,595694137,698410698,133412766,986194890,794689686,181341767,339005619,193242015,520651369,285792036,346549437,295764481,399914,549811321,687562820,806488193,475414512,508153037,662815640,567209047,989700,506497949,466641013,889367,395434985,143170119,762842183,649677,747235,958610772,579695167,973468,341371,356230860,944576,563352904,882831849,681609213,215755288,706064039,604060167,875739,751672404,303274553,331125497,746223528,896512150,964650529,943541876,953596,290635032,981292894,273882,835939572,556141259,727480169,321704456,31395,146410588,817680113,739430634,399016866,409561,324288977,675689,295578194,126263,488770,735622827,875667939,257600629,373893,774251,498395,316697709,185038364,352898087,200320913,754004,724346476,425033170,807267813,732996572,194619389,680471929,117474847,979588,687103741,720174043,695545036,273353371,243858530,113270321,594994069,754220764,804723522,704603255,991738567,848332,308205443,100149405,455399263,427776,144396009,581862159,407779737,283170780,426792966,134926479,208166855,754970876,790846786,350387,847342949,313666,145395693,209869037,705339995,925439032,375649426,108175943,154813,850384039,810175508,804529833,823385,606884410,797458813,465999699,807972410,143601119,345190095,919929735,928890476,941788505,358076584,711663889,465025564,643073036,851285504,582189,381372046,369657279,129332,106723961,585830765,463894302,403852794,473016707,920897682,518544759,239738623,998019560,307745172,968962673,109213695,161598713,700354745,859375372,644275042,353400,665020500,585876245,611255366,582376,904184320,616378,677124271,800796168,414954318,825518,110557,968686,603817119,702150476,920628994,154677262,597744111,803178627,536975664,631486,444775665,212720,514892,396091499,259466238,505591554,846530000,667151078,259712751,645431231,790454567,901200581,869231205,429867101,425697499,930542075,908600,496234,710033279,616328286,898722460,123050,249022710,411472151,245747101,398609994,611580204,403919295,610519121,427090599,982962837,617794785,286779795,102936104,293608860,497759498,29674,980925238,645162650,959191709,382156554,340577864,945732128,914354494,948530265,537178788,157860535,956596876,965811,721238956,754265,482030,546102075,314003585,855374720,263748035,941681235,644204648,706852681,337043828,308245298,240471228,73043,114809152,831508994,653042204,811418704,744853,490270,695426173,718754102,942899090,235259815,147988391,291074,769008369,705680227,582109026,647730432,366604457,83923,215715405,861354,887359307,641368,85317,411127531,259591827,663096,538753904,613047432,119709,141388192,209152898,617607216,368071427,720008675,306129200,336409312,429779247,929868707,789279249,487276719,601974904,772784464,499384,768603591,192795,399843740,512019851,565784181,802818749,631015629,210059699,776757,277231808,948181576,261928618,562024831,742773203,140835725,845101,911977458,463373549,448647896,509144154,864729814,465102107,452710785,724661747,309504704,354375,768000401,102096,278907554,621614047,571298236,781981667,636526907,380706,928108429,962789990,742657445,836840900,623585,655748,220792648,298109316,548585450,700073203,688147761,385271,377378400,215555376,768376,321288934,782628866,948572834,496282099,665906,606122491,274756994,872194984,769495,767114587,953742192,371951578,230630,452288,963836546,324767194,956550698,885982,459393318,926921165,676708085,293744,909508183,655800587,445635283,728768395,512044214,749511079,103778944,604248952,188748722,403563,503045155,449193,929479723,295981,95342,798910,380475418,778291549,102086811,682797591,806347,768590025,602275,237106895,521233063,433704340,779941,367336230,983445899,180514,687847370,942911453,210162930,311440,625345578,554141449,117655934,254259449,309727173,528494445,103652555,918648356,649075826,679763804,126167755,306152600,924930430,921056075,352508136,572902817,140094672,149491643,302035,728153298,450571043,261989,882274795,935761117,700928120,319746170,365595049,626218328,714487572,968514649,151952459,856886745,809712343,307869579,726529710,670632679,268689,879982576,945763892,928770004,916030197,731264033,561782685,414301592,551286,557465379,172316332,456349862,834745961,889319993,189962,292204,693728485,581758204,134439229,757251130,614343924,180130766,416437136,600373005,695067764,853194,931336564,868631255,878399114,535246600,865268,594244600,566061893,844049,304920055,513552004,112572831,249222193,338274658,962873864,230041355,440284633,573928824,799727079,110749891,316090067,761956355,842348202,208538,778766150,952543735,362971922,389773653,491161,258131031,505966076,944344546,816079117,304023440,912867394,962112491,209901139,461232832,290763765,808858822,934904478,492083,844584281,597255141,920359934,278112511,857355600,128804697,929054370,357624319,811409,647321617,613463,392571278,478372008,612905040,868766994,221432125,983606,236784844,233598575,945750547,904727602,354711072,626027,637869839,711944176,227196897,767245,894744017,765488734,276711938,944950202,865652914,738080658,513429353,141229877,454174997,286374144,780770,406056993,392136640,670552723,450353587,559825849,327567,277792750,269544,388375840,632092135,872358,65194,739830960,405164832,567663644,588265094,898193897,618196281,992262,488675482,962112,831469328,605065727,349452,413721929,687033498,322845822,834485834,938440859,411176,201202554,223729300,832214927,765230319,185434685,278485432,332362435,796440690,994030186,201754650,125115826,417940594,818008,198757303,925332989,937962531,114683352,278422013,513843004,284702113,386965521,744667378,736997550,435660086,199493125,176764797,222208495,416747801,225977976,522105,579712,522348748,917199881,106800645,130309,207198917,674454,817931268,183107392,832921,875823104,598717409,565203,851371,589522,964157302,977785242,905698610,416468675,637419126,823516927,166913151,921562534,457337945,333484093,300912871,679844327,359742240,462249,179852158,675509317,830993512,499193257,273980055,413700229,809177303,519852091,703574358,320257,203640,617964902,842672434,549021096,161279565,737157826,556389,658669526,832667001,343230,287747815,660352139,542121556,854423073,760365587,286530628,453541621,987046506,735585774,919513463,576317,998301865,853437598,296505910,909677,764403367,973370342,774868013,717190432,573067989,640530113,743097814,764883,764180949,340810672,390066,928956,966895,780648186,632211,421347963,980058917,888950915,509829,811054491,475101614,813353401,776481946,700335541,805917113,241720,142117336,207255576,912966544,545112088,590509512,480562029,184011424,629755539,627114362,485236766,258246506,700263522,104656426,311354899,821970383,363627192,983512846,899749097,787016760,849283171,882499017,529260995,726196655,599735,861840654,351362,410370537,954403,541011542,897928618,198996875,882846272,711568594,173372644,979129452,860721562,170345879,573851,283250958,695472066,930237727,410411398,275294190,621082400,679315197,924323,471124071,654819,674137763,952670420,898081,937302086,361281,572118433,847174876,220211612,259806658,125184454,720108619,157881,861689446,981978234,304188847,262033,345473527,901969420,323430781,137191904,866682551,509273656,805138788,542507042,654443,959635181,571100919,503937406,360170848,946540994,719744161,434527506,517500667,648406,519793436,870014611,551834,956311,757546187,702050615,182907743,915343947,250310108,245790410,289372532,332487971,660639627,634000299,159983541,383536840,216364,589114772,683986253,699365102,369211678,381267,358638206,612919417,438628815,820639998,953426607,966181108,138572890,32578,611453834,598166,196618196,726312430,433234116,849307,553368,274327,636212010,504462750,230899856,441845065,482508120,884380548,250158057,476222522,930594,162895408,471340180,353254712,723400490,953478397,341567,451143932,373639296,670459424,407358,282946786,999173174,173591523,757702629,966101505,286367979,548977,790845890,918689993,733192048,589356302,467522741,559358,646519394,762994951,898503569,290588500,134326823,760150325,505698934,397661138,604676906,181932083,578749,549015882,515418481,195860733,319347,330627,408402377,603052,453399647,397824569,415015641,61554,783982312,134543080,777511972,834573,650426971,827802865,926762405,246741657,774426904,648478131,297685173,792974,524303569,342935000,393440074,154161031,552575839,405363729,772027554,581367203,412419354,494066128,361582227,867288730,706570,438019304,745659,830490765,671798,869848797,603359793,616911069,449216147,349969956,362416430,846030054,138924746,899706344,982039419,609152749,541828,243971462,143221201,776923084,335679335,321523,374249480,457765967,731088,338017421,911401546,796396777,967949690,692403,360219075,841643856,60431,812058062,827943102,456533094,984360986,935975268,612752457,210966,203961810,841359968,876508,636591253,582124459,385245808,360883554,544178803,231098282,299804847,239645,637550104,103512277,244415799,790646,821527339,509549203,487577044,883239832,123756431,239935,928518009,930107664,317319412,557095659,706055726,401017253,781554533,762302260,453391458,120084435,319356,917306241,286326643,808998733,995637510,764234932,452520,102304,501554599,794466816,634163934,330948802,150702204,311771802,830245528,333024,542240142,610738919,221337,736972550,931382,669774433,202362,530006,967598,322402986,359698836,629186126,383230,509416268,777353834,899868305,114588721,816064888,942898950,683270930,537522,789842143,205704,669244589,704793050,858932668,629695918,756177,836171667,944567575,525323947,366137,383631208,215014,679507270,386851995,326549521,580599901,208313313,104233,329220762,866785672,263402382,359445651,619578135,934248535,226112956,932283024,846861291,847004500,633294986,689166,261235667,646090665,890104016,388832852,939509819,990545062,348027787,969435668,934451713,379885308,756789359,769186518,174620145,145999804,971972287,106706,725794768,840185,146573,534292580,630804830,376635700,198358,626923634,303455301,438544968,800317999,729189515,804568029,402315989,461025867,574883173,425686886,631921571,636037209,241990893,479768973,344137,257997314,723813,660124762,386201939,481451289,239845664,384906,781093688,130511,720469560,371453033,755616450,554882953,836253524,889905618,846864540,231926837,948443,909575479,94599,336499179,899663224,383387077,953364102,169371294,249621184,626301763,763630172,672965,980341014,864227799,831231330,909371616,837329871,106594788,895435449,895224194,748297369,268168915,979235,503551901,251876,381893269,285341,324534769,383235621,167952637,109103337,130533308,904223156,715898238,340848605,594460379,720921496,502250467,588713556,381999,392757,789315756,848679945,411077,667660487,491291,984023388,286081,753143,405504,855506691,159199304,520084823,728942577,133348932,548368013,639878553,887368556,942957,679534672,317435238,930464062,628888,157613927,94196,818894113,892329765,482791655,159562611,205057114,289038,86213,349081494,412883812,645405153,304385453,466542265,537192203,861135,617047614,887212,174672,854543,964310630,172365587,308609790,663737813,778678010,801563109,664658395,886324780,237766,389021931,663855533,416410919,931234,826315770,649316998,647275,226213322,631369967,249031001,284781405,388310032,718362121,219239008,918290831,86865,311638486,836850,795566,118444470,935348513,920500733,548157426,592050190,176750182,556237724,238724119,140875295,981812408,669827314,424159951,313903136,452215040,587929597,550772,336940238,524126378,509763641,160729844,613780632,969444,940370620,904502,911751384,216167576,624493654,316271742,77182,184770,386083829,469876315,992377,826575061,168327843,806443597,571183,744501403,339323457,446094808,206350155,362994022,538262936,999125993,897516705,692928910,233095896,713421,637667416,544145,615955755,443068,825495862,562978832,546810386,61287,729902,376290949,599399390,218133,454573337,305528192,883906128,408170820,532935680,453338226,711161095,314895853,71944,664449401,751226682,312470716,668598380,394432383,296501488,375733497,758756,740722,324416248,559248656,251404111,192972270,750693589,320844918,295943665,823464856,829571,654824850,951137562,185052149,483105,782257913,727625574,487588,726024509,968722195,340977753,710866,501047951,845657602,878840914,133544461,290656,693604939,294180244,569419020,636609,821862703,223138113,853799,300268435,859021364,715395734,697507890,714673824,121685419,384401050,136799,444685244,39297,206232638,230206916,632002163,192449169,199267069,388262,563591229,585722702,856512,962916,721263316,666246121,442104414,754153880,561499095,139317,457571777,309842,484392108,849757143,176220,796394541,782110,808288,863447259,254646045,759470975,304244743,443211526,443576969,796350739,655275796,746164558,243202330,250725353,260224406,82932,711593226,628908154,245505737,779266,224185623,456656196,988163660,313123481,488099207,871025649,807578085,127772419,493181194,28895,806733355,914138570,136251821,103483069,836646059,335367559,216154287,109775171,716814,42417,743074545,235768847,189865687,927523769];
$k = 5285;
$dist = 8345;
echo minimumCost($nums, $k, $dist) . "\n";                  // Output: 1232118232989
?>
Explanation:

The solution efficiently slides a window of variable length (at most dist) across the array, maintaining the smallest k-2 values in that window using two heaps. This allows us to compute the required sum in O(log n) per step.
Lazy deletion with count maps handles duplicates and ensures we don't explicitly remove elements from heaps, keeping operations efficient.
The algorithm runs in O(n log n) time and uses O(n) extra space, which is acceptable given the constraints (n ≤ 10⁵).
The implementation in PHP uses SplMinHeap for both heaps, with negatives to simulate a max-heap for selected. The helper functions and closures keep the code modular and manageable.
Complexity

Time Complexity:
- O(n log n) where n is the length of nums
- Each element is inserted/removed from multisets at most once
- Each operation on the multisets is O(log n)
Space Complexity: O(n) for storing the two multisets
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!