total-hamming-distance_test.go

package problem0477

import (
	"fmt"
	"testing"

	"github.com/stretchr/testify/assert"
)

// tcs is testcase slice
var tcs = []struct {
	nums []int
	ans  int 
}{

{
	[]int{346450570,966562973,457581303,222998192,364627507,169160189,954431542,221061882,240341464,2245441,231904888,735611889,365662644,741343641,855432971,6410579,954376059,436042748,1757003,612662010,619293283,756454019,412485671,362438559,34216799,142080553,739017385,767259094,477271201,645653662,266228943,301408300,648353405,543652957,779813961,33523464,581122512,963411206,25440862,235321881,537459840,564290176,530181458,643091781,951346494,264772743,242353595,253371384,100262534,923703199,520381430,497283426,629165236,170643624,116719823,850474028,58812742,416255752,301680516,135541845,719123095,56870927,992425752,194127615,675165512,203169436,169712122,493351238,319895999,340486752,309900187,844598934,307377068,388210841,397263679,76973008,693168540,777845383,514392792,423470900,514610142,136010125,792549045,323715552,111204613,498136379,79844425,353928756,743878480,863304173,946695057,190460954,119598426,632009346,519938738,292388501,523930549,810762921,501651610,30789726,732344533,285785174,63479657,750706287,447118062,460965759,123491715,56051003,96864966,216879136,807889793,812134617,933426165,725513820,298625074,322335679,541999219,548221737,257888129,496763035,472888287,143945709,667418150,989758769,467300921,578882168,171676666,92166119,138726055,549049390,928845149,41789200,916910409,170593191,269092392,35271762,107017362,196990595,194125069,632374890,428207227,661163092,87697666,553869198,330979619,791810803,8005562,405494420,972083587,546238911,144786252,323565313,733621387,271033882,246618065,59358323,995901031,414061877,83929037,284525936,374303061,931944164,587326777,11794358,659279382,640438401,453145421,831057063,135396331,66447875,97938685,83005193,144370426,363185828,708665000,381327316,669975942,821874551,423739731,530864043,230395994,352455617,961656493,598750529,91771061,502963681,814951975,247143259,503380715,381591472,814678540,739467086,735449213,926534406,652815823,174563216,214288088,2797575,567181369,84843397,619788927,142303070,538398379,158445973,121745931,779430373,29010889,900202132,674939409,698023609,127116549,287567434,100636066,759204582,751062847,997371041,705221252,484313149,681051691,140910705,404734872,298283655,819536065,775511175,938064582,373977047,540572738,550180756,616360688,860453735,284023825,525258072,854626934,137227180,565734538,35769828,35561683,123225824,882188260,710986932,958354216,931955812,783094713,338547506,283752439,259040864,750448779,621169822,83190287,960277990,52570725,733374736,66032750,710867398,889808503,728370791,71096437,709887505,453132381,818915205,285156812,594522827,696722476,733810688,950627073,58365878,141242023,678229204,948011930,55330417,870877946,744584117,631021928,104273588,765494720,888208441,960437590,587484278,511430018,374757232,768240151,140532093,483853929,759897161,299314796,970053676,789263086,138198883,278804174,845413242,108549742,974876069,234843651,89782818,884775441,244065059,100659421,358753489,583292494,927076681,383918582,124227017,529369835,94067324,441550276,579488347,415287462,207499662,726355084,552847240,334800689,588024883,214465087,37157543,382062502,348366584,956755566,980732673,30022964,523256059,212027726,667599087,528778212,888077798,912204336,532519219,486156684,453089731,102096655,99046632,376917599,924811390,611373322,789655606,85810160,42810561,696034138,695310735,274494749,638372687,301449997,556176306,806343198,233811147,916357266,256831956,132554022,894905815,854052764,77086578,454455883,233671780,721499744,199021377,320244860,554321216,485595204,753713606,451520967,653167518,643050140,605991276,173416589,477302344,169074063,299890438,907450535,92280751,479388923,878468964,270783401,331751192,667714910,327931726,105480680,932758563,35523819,841350645,547958667,924416511,417092910,693914562,785840324,386874996,420553234,869521561,422657892,882770215,547464960,423638972,984891177,55039341,273730908,685398882,396727266,5919374,141144565,394757667,908102264,101450397,767785239,84760697,229850027,913806483,335495015,520143730,442721751,941115849,909992566,659501406,77028475,477918762,791793154,858862466,309369506,515377955,155741334,555013423,589121440,109924341,662462767,456498921,211273094,76422367,28479841,564812984,934102348,352703266,621904520,339336269,301085229,867971471,140099026,2252870,2259022,460160755,626175016,99118543,585525776,954625256,329329433,767400690,709591526,128085691,750572921,353119347,25043299,143415128,339877871,20876877,837837278,480857967,798887708,837947312,182715758,2129496,430700920,415966981,97778682,334296997,505386605,527824928,691597717,501332055,102479782,681768336,300661338,186086375,817514593,367391045,725808190,951134370,994571969,551353313,203194786,595769572,530434290,597471911,869853383,704622952,18619637,555110244,861886918,749210389,75364140,215706406,218148084,453240937,288910828,56738907,921049259,12768437,643734537,223749773,318568914,511005627,684468636,941951920,929452334,509329260,427055878,637793272,300640327,625933076,682305326,735917680,210124687,895477319,514880835,36075013,722355037,896050368,763202212,12732131,33539595,59257651,303906727,44248123,441839977,799020691,925508946,804800201,424969401,723091263,384898868,774529712,622485117,360011813,257107492,261498858,52743222,130543099,102556237,380790365,235375073,76952715,352104089,141471269,443220854,739605382,705285016,408511050,339997891,38053017,192887069,93123938,204404459,244885791,216821685,635289414,20488214,748029178,757125108,161081681,115912278,369988517,431847154,353368996,280431817,283921732,163886090,359479176,687990599,799020523,715663948,901045767,969010972,444406134,185769872,940499613,142848702,118900815,644679504,73424613,37352244,713939984,198175299,778092374,370603235,818972923,48201816,112543749,175653592,212884697,245346577,371317399,144046811,780682308,949951033,79074764,864664702,190785843,137556908,19527162,213970899,114252993,985630089,589031443,99333478,341444536,582011768,83772691,365828852,32812781,374091566,672314993,332115415,553781352,209056966,337181070,940382704,325442786,76055393,510220186,368463631,572891916,70737642,329092303,76924074,663713380,793693720,234915454,149092192,472033473,661988693,78671791,972821941,425357776,808058947,360138601,240549761,1104404,381848852,845496906,160185521,86536687,575669390,861607995,563340244,951564932,434071493,230612570,490459733,114495345,970894281,239430861,523104927,26457271,138238768,949151369,671507445,792041708,386837181,139501598,344193640,689046109,211624270,536186458,844416794,541117382,759572807,497369481,75491621,210795926,292089310,144899775,670019883,412907291,213176380,645674042,401734181,50772477,574991658,1363084,80011249,424298921,546257207,245265702,952513499,196767886,100527269,78137050,929869611,873031436,76563479,459687000,460730741,468511483,597444879,415526559,138057069,42819923,60402694,221291605,953812278,550510069,63178407,775543409,125316351,657937197,350150154,661424076,972067038,268099868,533790070,370512971,301905875,775666911,53530818,44293680,853011407,109373724,584134592,47832238,757540088,693199600,299870803,577445090,641026837,960076107,599985369,518374118,765623925,119294651,382956706,137846261,440232092,899606329,398696623,538142699,156199507,20097515,416980604,746849845,56406778,781408097,56363452,846206593,202993048,500126300,164708320,939291835,525581748,852198525,332167832,80248802,121884898,967565095,913355159,340027135,175051856,836925980,197058010,534190396,656341112,294553323,607893326,283421303,136089053,971608294,354945470,6426571,75669956,474631468,376817718,39090001,648629403,887384049,137266775,83724056,548420407,301967525,664334814,707738145,43082282,381924535,177038862,227302539,693343538,778574544,884499837,906955925,369305069,682554853,989255744,395872912,324672156,801957443,891375929,509317231,224884475,62152605,921779793,405951493,271196332,36452990,425542113,758727259,964124705,279800320,407769888,768190039,298299709,296377065,987732640,566867748,901761122,900059153,212353581,701793131,56963393,399018167,854386835,249366934,369464441,6614988,94910828,378915053,136282416,73976588,517440059,99279841,1493968,486800059,528875121,369343714,332061368,438392001,37967950,324692491,350749210,199361455,593484865,786069387,941769543,366230811,346086753,87320173,297290219,509747811,812170172,530999050,351974996,473793934,978264240,552280248,749805802,552073618,571942686,296898208,9164806,561555505,665722548,409063366,32838315,803241504,997752686,677077826,924154707,666425445,130729941,302347506,608224540,407684060,473162490,103003167,95386865,937217971,822866430,121402330,299495660,69372699,449288928,439488622,81986499,848544475,48091598,821636314,921679188,862566905,647355085,737736471,359268897,655820162,128881261,443837451,10827857,595166251,773331409,809959419,89116800,989955641,628644978,809580584,164487896,736614383,34710126,405019345,429949003,17904913,866119367,17020381,32175572,194916716,845662715,799453737,406757058,925425405,548210261,857989575,671075998,190184342,972569258,473481889,28691219,176980805,44517118,667871648,814743645,40708243,76618933,830175887,564878250,31028010,235195005,198033486,896629999,560620772,135534193,28989440,539708789,62175442,744074761,867231646,590762133,122269250,630413149,816964592,506437404,215755967,51119811,763161833,334082278,398593088,945513601,661082785,885461564,683811016,626750815,186637748,140000947,501322764,946325945,429246511,741518682,649863411,945498613,763684538,529250625,237988501,258185593,53789542,97700654,815858979,458773958,147619376,488218725,750074466,772542172,430155042,185835092,682147084,223828033,633884734,827330149,128683565,854601582,711136116,111184635,955344711,536307736,735252493,767745013,408682315,863943677,957420550,65195457,316364407,760057055,46191029,884006414,996908730,170589794,4977591,699488282,974071896,958514991,486617590,757085932,295629227,156237609,660477829,100879238,905734161,102932569,701824857,590182275,759509010,425133302,537313145,453292380,360534751,101686801,800565042,904591017,69980537,489330450,107483718,445101299,131989792,794805371,945586057,85872199,938016387,563963682,692269163,694401673,382780313,320692757,846696576,995686388,101524270,654863681,440195692,287831529,451334859,465712587,446534972,605411786,171346394,836251909,752848595,945666619,292394086,824819066,727100877,202488309,252407446,931742097,338670355,200991935,872653392,519733981,146004896,916435707,782211265,877327568,414693652,964753227,898929917,560636952,259987806,633317444,30305354,974417495,117525021,351051285,981368686,189096642,664443112,380418984,643046969,552696279,92566456,424739073,353957283,430353191,221158041,856485777,166546776,773450769,461537870,149026704,518860304,347017439,903995668,801368129,724193766,380292544,665453536,182745976,510003422,20278377,161760944,1888706,678710684,450311702,656403486,549894563,455787300,135960829,964031173,855291643,424089461,173346634,449052306,757549962,504646849,186669140,667606291,4360909,865310721,311008941,945053167,719524557,568813242,594445497,544520813,126462802,37459840,167800887,376457876,433676448,33542196,895951236,890069266,23068660,167912160,99139540,583917286,45042659,556199578,49992055,550362408,728923627,772676501,333317476,74962687,472463267,88580441,565304516,605346084,421597949,41155968,804576998,614058805,827411800,146486853,426752418,979991993,318832439,645103008,748805400,711164958,448448482,553519651,898594131,566554013,923784271,882958534,565058746,562635566,638438599,54727912,689016068,61230252,245157029,126046388,42767174,173850251,323408637,40830080,976849745,194161478,37279531,77809749,723888998,907529131,413243723,218116641,924778436,412020513,134462641,199284152,441736991,215618636,890481341,299340822,259989011,653569879,963080526,910153043,416176120,317810561,650268638,520719283,733127856,566192953,297899792,810401565,870792259,97421286,769993366,335024118,841207370,287419389,759927398,807508055,484209923,300637378,576369233,886451061,134417919,9167989,615052186,136275669,606074690,782377109,369700382,884129503,125203328,551338214,96909540,404507863,777910686,257435244,327575781,565564006,464605798,172085072,366311173,903752309,6200710,929096492,764122285,444013513,822418244,178674816,598472584,508295318,229461860,832334655,133048605,410406286,773953216,523251433,341299966,299707425,333539760,663406228,926357350,31540700,823567738,963846229,687400060,463766138,299326403,17648878,271949260,806012004,316905952,478890704,94836819,75508015,486329884,216578484,842777501,906807342,812532813,390476818,33854894,63520650,878149147,190586376,287103755,750034054,93337688,63459906,64246161,748437133,964152430,391269326,468634968,525373627,294771103,120638139,926596561,549971261,597366939,460094048,859535536,884238761,814018887,744602419,938623642,825658810,955776403,349304239,329032553,279727246,534120239,477212413,805087393,602332982,172516516,382160962,3183804,409059809,766034394,368574771,86316827,613923173,695328423,571776965,13614077,616999066,852254546,919207710,126625452,37677587,887012491,980437341,568366756,532806236,15084109,701506773,332090359,925643738,922765698,943671299,909767776,176423170,262280261,507902983,870917034,254052486,662641966,173329220,156375208,471115506,266102853,329697317,507976137,100416312,360766398,847494283,370362408,273382250,60933395,343827302,619949215,43284908,78449579,740093573,527397987,312956340,462733455,915870976,673690514,182681814,224611266,912779883,261297991,31276622,680176086,457002999,93377452,731773454,70573587,512282143,457015156,297700151,957023994,842729706,103516777,137695547,54665541,788230318,753314861,546769762,269842999,558800307,810771418,851482111,28815969,126170408,772666245,160944884,111732393,424095182,269499481,434765644,366811614,370224539,103701614,96767359,162355443,403698811,858054182,756925847,752564279,816639970,492966391,87201989,812960447,928249093,406789174,465199017,404898570,902072294,687476016,947380052,172775106,226294376,929017173,785512921,179180069,707346589,52135178,648565826,611823988,774064480,245781834,244230857,739742760,866713415,263766882,516716944,830787918,113865032,321663347,979533530,410400808,36389539,152099734,627667986,569145216,524460152,121865954,87646796,698897108,775628713,559020679,12574906,686026314,997537233,203442902,470887890,735528035,103812113,806440405,867569196,614492620,528605917,139799380,261069842,491743673,218838455,171404452,19054137,60795734,384663944,121129338,799264988,736441331,421192456,668486058,403714280,325063087,929883819,318846714,678001511,416142973,553687510,779338119,833002980,835190067,86339277,198261745,438011718,881981088,524014422,72932785,361133636,784233830,510839171,827304869,703802605,263433137,202432023,660913713,191352107,64821368,116996456,411898987,91975159,785755120,102335015,396153014,737379176,796662773,98170413,121163904,587237172,7791839,546892762,189620352,876502494,787081885,778954253,823818059,83045404,672713056,934414384,947619955,909857533,891990491,893821108,803251391,163923495,633639942,215099721,966032946,139352102,126581662,887656213,269076182,910313939,765850123,419015721,798344334,295395082,870434957,534697513,235016874,706174485,679936073,718071802,567658652,516604190,83215087,377091590,347089411,759124003,189750172,910903587,145667246,98045942,738189945,745376896,277378121,500060588,414791805,466927051,530678597,408572366,16030834,994771163,958744646,51461881,276902804,308363779,791993442,930135588,255361003,973029293,408334124,306864834,369028591,123734979,642600335,281548160,866429357,784571370,741423010,396409176,747726616,759911446,746424213,699765764,135723154,57373320,639188893,927500935,717399550,361042592,47035900,258389204,535417394,803660028,589434613,78455658,842263326,855002705,10359436,750822601,254523813,787278845,148798748,982571106,716311690,257248748,695126225,675423895,250845223,445263900,717341152,172525984,334268216,21664338,980771001,526718013,622051557,870124903,973092298,319775512,462945390,182895227,663959910,642156136,258346508,965309369,508590276,891853672,96292891,777906355,391665549,685503988,15760161,740537346,543439857,138704486,979517785,938753171,62190488,558479374,504796359,552000063,128682379,41689902,395492570,374715103,60178048,95138646,705863463,747556613,404659741,828535516,912450264,370863821,110695953,539022347,55541561,917586438,795194359,40856432,272264162,803602624,417624163,825727723,759492125,934325685,811360931,22008867,535840385,470418824,87365292,617131743,580168169,310659003,506096142,568111405,536089273,358512146,467502918,826362100,684048129,109920290,32851119,225459754,140932170,765497127,135684312,966082317,614625430,613259940,285789627,138321228,187572942,825420976,105984012,9346321,110289394,148436175,183773989,607948737,67230333,363808409,641987054,918574050,214120067,680857344,22004323,459469377,98108274,224277378,389070139,807099636,416867800,998436664,80772768,131225450,833411259,254684279,336747260,884767553,904470021,183884412,316344451,779161632,807248196,766232073,395998430,493790957,267802291,620359303,345699336,225475017,42952342,345506602,133678326,463730320,697333277,262124860,836540601,955422676,53686913,165793629,211022,837636616,403299027,581335435,247040773,928382160,850267665,885437095,272560533,342259080,387150894,762603626,896736886,416608356,139950072,439245217,138562311,944487629,951945626,389944610,471948204,376356257,873249562,595123514,55050650,818306340,582359570,279808542,900462111,542417746,139954085,506691708,987854579,468812874,13451053,379043414,939140674,925481046,335884901,630506791,36300617,805071327,332311720,705595840,337562724,557885472,467525102,51724941,757689999,710765061,524335613,28738981,979716739,135089402,143321691,916965859,102541341,923411871,711977606,428742958,75259421,810199242,972338314,532468306,630461893,488721353,962313743,700711622,852889384,58533163,219360215,705195253,47347956,1125680,177908093,597061005,406207182,273594061,532895000,359457010,315446637,367482194,110265786,106161588,284856015,626973520,634673389,404374274,680164010,254041667,273785611,250287134,802880312,15144614,132457152,59790303,20759372,448887899,348866582,770287364,188302632,204418924,842504115,252471065,986630,988378390,889591185,577895881,775020233,69715554,769201972,125988464,69238506,902917315,4842081,362433937,956534845,211537051,10758950,23003458,658019302,582605242,468355621,918334470,275444879,220316999,605994765,586561281,31004968,409454602,958869404,793764518,424817440,316566383,214205462,761586040,767016738,698961203,705389731,375477477,135979631,73014965,387827827,609419744,168124865,379105181,36796418,109590637,934824089,598102371,83081437,71298265,600021985,779274161,905544521,63136736,75178912,604568126,24338303,470439100,782649093,438946754,564745611,594742915,455279267,187384786,958050378,913296418,707272217,595143552,391829316,290452310,194623117,206111616,19786079,477643046,452801636,702534931,432472689,129317506,185872578,519195708,689185173,401389271,903342470,914992647,944000540,207891744,80647739,384368116,444115436,742459527,282776150,237442239,667094747,996775489,78691954,518722904,539724355,969288135,14738803,754442616,173595224,125115720,19372783,766806693,670723604,709949325,699162543,941827464,985203989,224524753,251734470,151431278,130346229,88729441,715042447,192896695,107424473,596854231,225923858,144172088,531707778,526148257,429075631,224043591,961800746,875727053,639146880,221388444,79396635,831899658,619010036,83867562,251315611,908624075,281593286,477378392,299729152,698705449,494878125,5460622,227855711,607592176,516960547,984561314,953482841,456113351,173449045,22790336,578066564,141700698,797245341,151972554,637637373,620908059,771685418,856054671,363399175,206442157,487242794,527471325,191043037,165249172,439456811,547339022,99977584,991042334,565341406,225356314,195394668,495688813,952813378,148888367,548335414,20973821,112670017,357377643,81768889,486140499,181068436,232876053,232617937,982408197,125783774,923980970,893911333,172179319,157341924,686325789,735846264,802814553,264438170,268657547,109745013,381937874,194206013,638295629,153819838,472684856,872364539,959948904,964073264,208210011,927772492,986490755,376364445,10865278,662574507,980008032,588399912,75126549,79008254,185304641,563813137,309542995,76702509,87354072,428557203,893737361,543199209,389100844,323158571,132938112,700834082,763590957,310939827,137959238,191552884,351334535,446984142,357655966,110071187,775998420,330235287,959703339,777324534,350418237,872127763,68400544,142665372,185157152,25427739,807742198,478989099,246572868,654237413,444906229,793910527,938328478,514309825,176528178,27149717,477233964,19811403,110284936,280531991,174567572,287499380,956852488,462217080,827090939,48743320,830688311,380232408,447726362,154267046,753480193,30537392,140839358,146068068,978167511,867018170,90816873,84268650,904455755,91599397,351247636,779451227,586525489,783953893,100905306,196375390,946297938,958532862,786975487,138206714,55914722,308378915,839362772,143010439,335225858,84367903,70612210,368440326,974183359,477368563,927511727,105802116,99703896,686135412,38168741,990376690,115280933,496391337,22716011,121864867,276399009,431015802,620242883,536512043,21556595,962912978,241657454,645252901,120573404,838595416,337981451,360000642,69356495,383969722,190758419,31146809,84366151,395671415,85595724,940773425,449839692,313266004,224805362,879984061,172236338,115660257,15196020,434911303,312913711,100772921,911842920,900651448,784142480,768498299,184258235,949715249,765725439,470935380,533692465,523044314,155218227,353088662,863825573,326951691,459396542,873970429,32854723,286032182,274480888,198389438,82159253,18580150,891452235,791792173,487869730,533987864,399869435,129262582,55743488,577932724,246756887,452077452,268592678,226513152,665523180,146231262,426001775,101353327,490834818,976097999,651489760,716763914,60821506,24835370,796236072,369057647,612079171,560936445,998599363,874792636,966785890,909180028,242582191,947900709,126501295,684411691,777855883,336361223,46116057,623952010,598783769,650435741,181735757,504100443,386136664,896309192,818289886,305817192,734157251,332860473,191069276,813269467,34002361,832988381,382803252,706228530,440786741,631657484,48645045,971958964,953688866,623808232,329790570,134817083,275466396,936458287,939759324,940218430,859456962,711129190,994779353,889372554,991310536,571023704,883953263,310621295,79359208,202864069,479859894,997122551,469312047,20138498,312803307,38191471,579421222,641622656,29566383,291950133,953235583,595415439,666466831,33325865,762064835,224189715,63201745,813280106,65328387,610056692,135891666,949092279,678381815,572482782,991378514,920551372,27694794,48408515,498587970,286821196,650537304,534200029,463737874,824293355,481410688,498534967,188978353,30864958,203790179,658100066,147027212,125652965,872957754,192695174,222449742,91268014,76660849,96184590,105175095,91758762,89232966,587852534,258257669,472192296,183843207,416790594,55340491,833170242,144373785,981167032,740360089,711765105,152205945,265272616,53784518,658757217,454345834,531561884,428612868,36320438,345224296,476907256,971280988,296364469,776031668,889034423,603310113,562771704,779026318,680509445,971821840,442024376,957752459,555644148,97793211,785507322,439582745,516428113,271372595,851421584,952000905,171535116,67640338,605290081,273334106,251777187,869375897,914945269,502223563,53669209,661221079,707780106,748320809,363600031,80240233,125349362,651226583,234010300,968554443,568479241,275857984,75426862,122391413,890628112,618637372,115471008,543498215,119527392,438140908,112815193,4372097,53347437,548166369,327318153,530577504,856985962,983221483,116801116,276303254,969145164,906792500,563083319,928393751,690572533,450933743,166606916,636740102,779881313,372529950,989017223,682017759,197746405,366626926,561140617,135150873,590507632,932816815,14565183,569852079,519804711,394301781,42982272,287013621,589656985,875399637,224212040,290934373,61226439,974050516,392159909,197256498,368189496,260472265,978663847,619002734,961142848,348832180,985071528,145736373,52842009,643372561,582470082,344205148,527955996,101479015,41746543,992952788,462087079,996669201,646814607,450878735,596592529,122465638,783622618,621112253,115628104,36327040,101679041,670142722,329978717,149520065,220844043,667067263,180346832,989779507,815844487,215206914,620142050,989295459,270384339,67167099,94013149,678514698,451342294,590672632,411004521,445575695,308207354,103420692,670278599,466179809,63705607,46259221,675604289,928222112,100803154,419968951,432390346,99883774,561861311,510436696,505358485,262233510,722158926,894980085,747803585,53529429,459422266,99292275,796429362,115693961,788680570,878249284,873588935,856514584,857727447,914963065,446815866,31429950,548149644,839199656,903508543,204192842,983206166,6851944,782463026,813707401,597403089,860645676,215008918,587390572,83996923,632507360,300125448,562296311,586052177,64428628,520192708,472916419,469276586,571629118,321728126,68274183,166399692,655915050,930685299,904419192,477085056,457576872,355547797,392318225,710589863,520245052,145640605,236247811,712674752,408257545,167285228,299711651,50061073,710347934,749111643,415740118,579859535,211393237,741160699,75694071,318405782,64213397,636246094,67023445,974587665,830088564,37702814,749476189,100213799,666140545,991888004,893615214,283253158,812064754,906722371,531908863,610816558,22057646,1163969,235474160,949329346,367799590,149773064,178030942,514300501,19819710,42879263,57730074,192702430,137379912,192239037,939068349,857398418,472918534,297801969,166290404,966595281,581859,627843134,572395427,316181607,189726171,507518780,63089576,637065861,605440463,860342155,763203834,247014507,486929498,911377816,319078039,477934914,63259818,996334439,462920614,766484995,706396259,905302975,298440408,159116442,652900179,799355930,910398456,245865117,496484591,442552342,34321011,746087990,343833097,71850849,149883038,85901735,641449361,471502387,325960879,193709856,96340940,146992389,333361382,19912251,805237272,973865688,787744429,176913026,52839112,594682682,442943236,368646950,151945633,185176126,344323757,373933812,168427162,164843566,64887710,439027872,135117259,464030643,449894644,882339199,100335058,349635489,601384009,48491412,98859271,168403497,121610980,97266072,308795315,247862984,862380555,455832860,901687749,666879142,520585901,638860229,53117450,977742154,367515434,668930466,637450017,974004483,618483278,27601866,841072688,171302662,101248185,871196871,662305651,963333956,874583759,751157445,439795980,12322886,952314890,360735139,529145692,621863217,999661817,197082769,950314909,106792824,363642654,3626416,819631596,588122114,494121435,379695096,361563235,207548213,749373163,870644533,762074051,586104449,149985554,808888147,57096050,835605788,276406114,550429537,857160730,773063612,397041112,631256733,755673929,186414923,689948466,699657909,323004169,39892414,42861390,402833494,554078314,698108584,53302658,357092207,579413331,154493550,265365627,824041817,341757394,190743811,785630153,2014646,647900617,169074560,515264939,403765069,824168741,534506837,532314058,185499404,689711231,652911489,989443100,249797910,22943485,211579582,578093820,806813712,906310426,257821611,733300078,958739391,963141096,928153033,939792401,348659922,591920038,48804340,501746382,476139083,945499259,774541860,472151484,497915923,876629149,413783754,911504492,655142993,632603760,772836601,83655951,196758250,938575017,8418435,902199990,686179041,623957697,694365178,769408848,455469749,93848466,58171164,370672541,836315218,669399311,74876991,618127751,140205449,643420584,389592643,998889776,460796633,575958327,68299791,158319839,942274018,255007548,327478402,76398800,425367850,977372665,599964752,171864199,949065956,590476223,404925752,4415099,983103473,73869271,68268309,422180443,93714391,745234864,830708522,719918685,543450175,312119112,276344341,659694373,818236128,756811555,979142282,277146613,111094348,999417593,741882364,319815844,786300245,881337724,93908840,72876982,216231193,655330027,835621973,548427409,419650139,723589425,167573014,48585081,318649085,503934555,100045764,575417103,709366258,282468640,511572610,269312260,583109591,509607,122513908,240391439,635153844,682425449,961846363,287906903,570662030,454770708,436989683,91529441,737023635,470557549,625937789,407011648,909352241,989482435,910901255,106473322,643244903,584405723,664268730,390042935,331517901,41760367,225292756,274659009,44585438,461620819,395666900,364217188,862863344,980132995,895674475,533514433,32849206,986286541,91623394,168608059,264717220,309178534,600678845,81701946,715534567,874022947,915524749,504125688,17450801,30814993,949985580,659706193,223916290,969736486,107723119,966725190,36478775,504405539,425939264,991193175,746021024,11314113,177736255,856463386,144726308,902043661,560746254,97026520,223107076,254178670,635932807,96576130,804863425,133070100,771672751,643160402,104659641,811436550,85915978,319304971,144497391,349602936,54265738,156687169,626298161,375837980,752502611,573164472,356619040,69346503,570539247,331619052,594321577,609281020,777052822,871700525,330262419,268227216,526644259,529951726,76953351,8288272,862034096,75347388,934155542,99251177,667221767,629611913,235493022,911837911,816465185,57343612,139886537,371412472,741938722,119541103,230108176,603044363,391278748,419969100,434894589,386506582,671070077,90670095,326380942,604236334,742877453,71428913,62382118,484237490,763955947,795854394,396646442,440488984,715201457,717894118,876290958,172258558,134606728,827975783,887930899,590756490,27427349,55449116,72873461,157053746,344906859,791215960,747897496,691429381,819592550,931875992,441559973,742465826,388643443,432575974,865228501,76621048,865722692,999576019,109580852,331894085,921833914,108541718,485511632,703624071,410295846,272293205,144244678,958749330,923164447,848489732,275509644,308822354,702307457,111305887,52764850,701066317,726302377,459979269,723423461,673183360,41857702,713718454,769887883,709654984,840119228,178885971,59408797,51238971,618400306,426070040,248683182,408041390,829335437,117315560,332628974,595232877,100136013,151769821,732292558,205219927,65554585,909777762,551279294,106641100,108584680,207573966,975182412,88583158,403947713,746382802,796749665,56575541,677345613,129883522,901947480,737210765,468167812,909312254,317420926,337102712,416398376,551278437,92237501,545464751,18381014,839540777,987256827,12329598,65123474,106546126,866861731,609030247,857278305,601662990,442357785,118906581,303115157,418211593,961245498,133608505,437732420,482786896,6142706,954223264,222522252,162459937,805424400,971442337,506168396,989505805,510702267,28348057,290381521,4872394,285947372,996562865,800087680,324018824,913329823,914204983,945138643,801614620,572000709,124607122,475343629,461205763,216776718,27012692,321738436,94070706,498391550,280557550,249632616,539814521,337224450,521986717,560054624,417240767,31463514,319281214,390708423,778956482,654259440,815114018,616094891,333665781,840978950,743331743,57208580,17887360,778127518,961268443,312223698,34121243,683554508,256083084,431164200,966884422,417723705,558267892,452407101,514036127,871453186,675224562,195622786,827679323,554800042,943289198,137268632,469439724,811500768,224765679,213031880,571567611,642485046,698391006,859506987,404415718,229229671,77417779,933005218,886087110,814449472,184488504,524879038,926653437,505886193,334465856,48432524,109128655,174270047,936469068,120955591,26582806,100621866,82071673,487085315,28205419,247569724,228527029,945994145,147651205,230190150,980781381,701174673,399958022,263639222,518618971,585901002,25619119,876782211,838813141,849801879,499422734,431797862,672401999,794425257,792439578,631387330,10155483,824973246,963899068,427981486,162101399,74443528,336892542,31554833,61101069,14440573,623015456,683484798,438972183,199152236,17603357,654361460,382280511,510455131,22216952,885641333,557704952,373987687,73904287,302277152,573268509,105168899,780601168,379209631,437782499,531486071,301907424,447195885,975958342,244736786,652956875,397740533,501523598,233797111,680454214,836533001,827689476,725441513,23823550,408920017,771055319,210420435,423663014,595986493,674236821,420023906,563040453,207944889,766834332,928230855,100263108,494876908,985006503,52861198,527408575,136403787,173396760,937014919,912160182,937906588,659034114,458681350,738640367,518663440,540312907,478168433,486024935,386267935,162118664,719121452,29257026,742059397,354747250,615405256,627872218,706705146,8820912,662653497,160109315,953226092,642921624,593506511,795368640,822513552,426011303,54469001,425444763,122565809,526734390,897299796,287502138,3206194,992389961,740071925,956538629,482156161,142797796,56302251,817601386,826120996,926780495,493866352,180460987,553877523,470897894,903665263,897723657,968883024,441467745,192389830,532984075,502035466,39806577,954704000,505296194,362792320,537426985,12096191,82714250,756480141,58539547,119634681,448368553,3131526,884928532,315076780,948251605,581559426,864173863,531189358,402997905,815345275,414885418,99818517,465086912,22738551,500694647,126981761,169669165,564351517,768161067,604345883,791088918,553164827,377518104,73059268,132428348,723165122,271742012,617762162,438202067,140714506,402185573,47383233,801047641,425697822,80761128,142613392,311529292,307679258,24667230,117790739,876511486,583705360,630686024,108207423,309466508,791185500,235956276,462318370,381988322,42085549,248175689,675562549,433719354,961684760,73833998,475434998,996844546,91849306,818027396,189115056,973927210,674261036,34026833,658332129,752342759,241036977,954314197,750833183,432375487,643127139,752629822,770737524,164207164,313318953,321740627,130894843,926371773,273948061,40122059,21580455,925454489,682519980,403145233,144003324,842774877,862705774,479337652,16757267,112007290,103826836,699384797,382283148,554775190,880106703,878975363,398918228,174712062,775480585,423938452,930305665,611856426,319249946,12670794,943110861,80420898,659797301,400663377,588143894,860177895,149969661,541774496,66269570,41628775,722636150,118727843,32506394,312591129,974104541,507179506,596340977,189598468,508698106,556668835,494343513,610171326,915061657,310873032,808314251,356065635,505686903,132482473,839865419,1063980,495421262,544029593,312979203,54013318,209231523,123476922,600403630,751130735,345386079,48510490,64998148,502180760,334279188,206070742,332816761,603885339,286155429,991388148,727964941,692426428,397092303,698645292,483819426,180005240,336588635,573262247,206944887,139669894,818239443,458021691,389169789,334433539,859785774,2042955,123689980,679280720,440972166,246106743,55504057,641761779,72839350,145276660,123401628,127915950,45219581,589265407,736599132,571365147,534639892,414064374,125896116,103102826,977377100,467482375,126590830,603269280,669470051,909299102,889353840,676784338,286469185,29255721,74631331,784287425,57105267,636010838,408043147,858865336,357605596,618007666,269420501,254832431,679254277,996544665,701221702,42890778,458284101,150022296,278927294,121712504,656096293,829352753,408345572,853776439,727859597,69393467,5358126,652689086,398999526,541087548,258152769,856621643,509584413,420445055,198840755,224993131,533828928,23599377,936211700,297360331,540636548,475151779,531750107,90088113,134944056,262017960,394377370,958901526,186155325,976357243,506614952,697816487,793500742,493522924,57938954,762886365,146742543,429166954,758909252,875397409,186766044,148788172,11841696,100384079,380552858,538562218,764604399,163990345,964209314,554340136,10605066,791180139,145853949,88479616,811200966,273939337,40981438,18734935,138418661,116119235,700831169,714632166,94259938,969803636,88829522,456641589,816115592,269679933,113117339,78562487,844759751,655723318,648707800,57518781,350511117,492699698,106881454,60268486,113141396,44414977,98671508,100616628,432510116,112858164,17575556,187110053,635580141,404748187,167563791,893574120,947091369,615847219,820514840,45913424,720287895,513333126,148038683,93060533,138756624,62822573,882987243,254592331,938860871,517799319,49416789,264779912,569864400,81388827,540889406,222947469,512126046,187997946,733033685,130944603,201161602,576763014,707772318,617427893,469615347,822734304,48244295,240531146,835725746,145056573,571883066,649369937,241615683,736186282,429551207,420093413,731244602,772092611,464317903,628401101,212728561,916136119,834981621,877954649,216625784,637748601,342833408,95441933,715262200,945823141,568554271,182382125,837210606,685799898,694152237,485476755,910424910,483456073,161077241,395794267,2885641,254328053,792107819,497964758,342893925,112551152,300075813,875564513,847799325,202236008,306951833,683737137,385066462,443798423,502367908,184708330,279032395,386156295,433268831,979679287,505633638,384741265,66158316,319266444,496974102,872807709,611351084,415901540,790890373,718207728,704683287,239691404,961588903,255743977,174243792,140696214,301773351,695819690,238566846,241011773,530710569,152947192,838509063,34130227,41570018,528085829,781593530,84990011,350489622,131433233,385157915,626343925,790488459,405690071,965422650,619525465,9264530,90133126,684456125,377174474,947142221,116011714,41209369,554603958,149694126,998803623,805801740,77966198,205843694,811788319,762668042,979376598,713306909,295502009,165568330,715599445,964427493,719285873,852218548,668694393,757716978,164201114,4615181,50914353,812017943,119969894,639842503,382327392,298384098,360197919,883002318,507957856,793167545,128910464,373125781,265730605,161271053,358225257,295231858,67591414,576002991,818967639,166415050,707015534,576039665,435347557,202583748,856450719,577326970,803267644,437087666,383824653,47551030,912201682,280892019,576085805,63338890,532318965,60949931,828769276,546287290,957892105,755190823,656786969,345620981,701541110,116213740,934671635,976270218,398490846,227132307,334243030,598363236,24988551,223265492,562171313,278189369,456825264,608174023,706128488,699843072,287555063,892716669,213792872,476658273,81591001,998365599,33866960,704787421,635366473,315618827,113995877,166270193,419887582,212305210,36305381,885139875,719634934,69414412,357380741,779331906,728581089,310607629,997158393,71708541,260101198,37108072,905108474,531450817,502372024,253885942,11020605,539714593,12239623,700397296,12463243,602284851,511062446,284920500,917794337,787364136,434800938,959997872,432573371,821479880,232955175,207916322,286708763,553854451,437631859,940141816,926310533,37665959,691580695,8221879,184640454,138240463,977639234,578201219,257363636,271543772,226404707,635866643,132041429,662668430,411088246,498236701,618472632,641653122,394124798,215912638,389322014,99900536,282053754,774013127,175670541,852251609,869845551,572990528,728109526,767961454,544417486,389845913,167652794,241963894,500622687,917550041,183469980,940920415,772816975,753801769,140297930,843243682,151976821,709352842,56985928,132268981,985146178,45873854,848213483,927559995,917042392,241347825,883769239,158192152,150743678,665776333,106006439,824750419,720834395,901402616,169616105,27077166,612374376,434501008,7020234,463429409,727867972,210152092,208589507,70532245,817447149,381343384,940030818,853745725,566154468,651082397,312664914,859703967,774596353,595036757,98914467,889061247,54141081,209060617,398543427,317882596,860960883,217725673,796230201,270383750,57267776,219815954,567844616,140112422,20378020,481955776,69894395,627499012,876682845,523273848,718028871,200622404,104396816,896125491,878310826,114946751,760718913,432620200,461051236,767125076,726819391,559498979,461428418,663972009,52525451,972454618,694211056,119542619,48566166,793723258,731360620,929028559,622372354,966792788,818093292,149145481,574683118,465203667,483051120,151988180,900263555,352770701,962305987,570356530,408178080,186222042,743164793,398763577,515954930,115541924,587899780,259342613,526976928,471647246,406101023,429841973,12030281,122448527,496038041,172816011,913784711,117056658,862187510,358809192,372009168,33190159,274232671,528595035,104389253,561992728,571678568,152834276,88213498,633523034,190689190,660593584,898889876,94689287,157464182,800653770,455380288,92266155,820031107,505747481,357638341,20869234,709381377,891078742,602441194,991235600,311574352,65002678,223811401,354350710,393208417,639661278,276941042,744008423,545267458,997444857,798363117,611080963,170945187,535616801,7609830,635351146,58017938,942886806,816717229,998479826,806196502,63258769,771682474,806574863,979921155,275741820,916037092,525139901,16010584,92902922,198798685,872427710,667158832,926368437,217879909,448012428,667211014,803391311,13570219,441404151,271049119,502706324,577498748,188351774,237369940,599449101,888231008,132699737,634927682,383309431,978149464,563702241,238692501,205411711,348406048,265521945,156311149,748980962,721373267,220806085,236128579,63247597,145441161,31676150,952592241,520184680,130968401,808156010,991476442,64438552,686985376,291128160,816215832,806929966,712707757,962972580,36366846,770698483,655528724,673133736,207827134,935209694,429493243,593376112,751236294,972032545,42881086,88369235,749006077,143481072,448198679,295542855,59088474,962537604,375197577,933689047,848804300,120003079,404604220,249899138,369777412,31289066,889322394,148271416,709636770,533996530,545518897,928412836,218355550,999659774,162746068,526482245,747444653,315926599,198774009,103193109,347279834,664596070,803700443,121205871,292576541,389351535,448576336,554878182,109104531,916301626,469174123,642512055,152331269,224109437,713969399,692553204,173311466,650962308,87307669,648661982,434939302,783492904,942997771,327200915,353137016,676511251,139146917,618499592,94769842,949825576,472507681,835046539,821547828,581978633,319851324,589634027,489544531,558059438,36866595,580045338,393722033,682070802,89240106,707854514,644390996,519437951,672617402,326757606,699398663,615329010,346405696,212365655,111742271,151641219,363857322,464067845,720643589,49031243,581864300,545740240,353557343,151012552,889774357,154478969,20302760,926071094,308381980,97897649,186291719,766742485,739063395,186044095,899893211,925355103,159623125,371765350,23286905,126945737,564213797,600984674,926802655,866309472,917147822,13309835,946054713,165617581,188855933,913814243,820422404,639825219,91835204,226510013,612766007,219687215,758633312,739662545,873044979,304180680,353608900,810509629,539540260,22687117,197769900,407002322,752610159,440261483,393580866,456960680,529605666,555690225,79230772,191723864,77511748,10353485,64846988,109118287,792993649,560745461,290719991,398570390,564028315,424050925,318650660,884910649,14517199,324911482,529342231,777610543,507899137,13298734,173523050,119108724,405565264,222296470,662709157,95586935,797805745,626242925,447486528,418344302,251223436,359438850,217252939,647945873,136713574,85019575,285845279,280685814,612387086,293612909,982224404,331742117,515191385,960521569,851435684,396001027,330417314,724063834,698514136,426964181,244125440,115482888,181638884,23439579,397970361,423780569,69744662,819946619,233241312,722053587,917526090,928409170,949719666,839961958,476111306,478651220,217312878,655340646,659590437,425888845,350822464,430541433,30436266,27171832,848920769,77497562,564907961,382897140,491225568,893960886,797995168,662391639,54029203,476210718,1985057,150598294,15286023,361634568,406441944,717250279,999728542,525551266,339887551,183568637,451564967,38170449,226104468,239222133,309980725,843696031,164671876,681282596,726763746,978778533,399046689,979251020,104706179,446117069,24167006,93439137,414008180,181443558,888079144,934826558,639598854,582285943,189843200,326941536,643226526,68522062,392039820,326404322,997183994,501984548,184027751,577959377,694713858,187222667,587821414,89728898,333047070,972699986,168638669,779179490,107387602,770141912,684153093,726566591,605656673,992194909,609316608,582201760,922463166,946961847,379433190,47654965,511553580,96958697,230689562,784464277,881973184,36666825,79004733,126127194,253389969,265136982,128688949,359133314,524560328,658040339,936174101,812917585,207867459,465468322,990645480,130845747,894193879,625962647,31821476,100119029,220824802,343683776,355191380,844468647,58105684,270150181,633662309,591021890,193037855,332416946,326645575,756955871,257177647,293110296,124742301,38286944,391057355,993984243,410860666,968266935,824278157,225977902,259511018,855371047,965653911,211361798,212765426,181221105,444278867,987255628,346683074,372268985,897945762,52329396,179346949,10110033,268116518,813626620,594221891,81342065,754960472,287266428,336595518,481923406,171346736,49021325,415172474,422379993,152583947,382922711,920997365,933564557,903984517,968458341,893755152,487707477,101968987,686771359,634606666,430444460,400611055,708768040,172658371,618834300,484777679,105494235,367598870,716734249,916746920,717800862,308937366,842335563,714584895,92754819,443072367,36962951,613543474,756178271,72956329,756837644,624641527,450077753,812368515,569582557,639420820,530530730,70855344,952804748,796822535,488323053,710536584,624784899,712247310,459669370,957401909,751896170,325150242,247214257,696644101,209540641,669350785,259300509,612313578,205647600,811003755,254381354,540454079,703362590,310551973,61748001,357029884,324929248,827935393,563601238,688618727,825571006,480054575,181180246,112066723,748212198,331153532,567282947,290076127,521587799,297890739,865269216,967939475,763108878,591551240,145383648,774065297,52491731,405722578,718789221,94922972,583019261,984322013,79034581,189309021,86413318,88163763,4648311,814751685,175836523,139922367,973607282,739682081,846881462,15119518,710668680,51943793,579441778,987107348,795003339,770845517,979245515,657678575,505478916,138833680,210419118,401528195,90754491,390319445,329349108,305099837,414990001,857544998,789004947,887602582,515183612,829880758,47096088,708442429,142565235,295133171,763464074,118879471,640455965,748343569,391622282,105799166,636080402,222700226,651680239,623177173,461000192,56712215,265415393,305953910,884493030,585529254,13080002,230735129,757330268,107217085,51746340,762837923,539599271,221506416,269173461,43293376,782297746,976308666,690181313,318150144,708167756,821103418,555230704,945995913,531871050,122777114,369127387,636715704,369824127,816428071,433568614,368659805,367999618,9654944,2348861,261074690,573224009,564278821,546359395,22277193,750628173,488761133,276391134,91639255,228162464,113717484,136791405,684115054,294266540,82898739,709703117,649090559,841076931,242614763,347854666,942884328,775069483,104481726,968702792,914297237,348167974,559179521,741770175,788760390,279321799,162223451,332792914,996067388,62540329,434279629,788292097,791634514,133062211,284577259,443910144,439600530,22362030,821978563,231407190,167757613,3656827,769222782,475742134,716428357,70587370,950954446,118072948,970125786,208237278,238565314,215263449,570325795,39098582,585828848,605905419,84923059,372711005,737041314,767688502,458901938,151095589,930872147,542784812,866781406,613513041,37669418,188189617,452459466,246651035,820506535,260836358,655523957,593014767,120561820,998408197,602327899,87086535,227030138,410067225,724827352,646059280,433978306,811902308,323976096,988178905,477309015,281193560,201634451,141022991,498947096,673179515,184256209,915664267,701521067,779351039,50149420,840690894,989920423,829714630,47961370,780377965,129825526,927208708,455412724,282912938,181933086,525641652,859005053,558345568,757907633,73572405,728313810,906395348,685105665,556575019,65061648,7898769,196581625,910500867,612581725,624448357,350953210,480505808,115580914,681678219,140569988,327776616,646030557,158252267,161096483,364689492,417963506,293636005,222915229,324773435,356669949,924974066,405006629,570736260,347849249,851840809,762485961,859603456,25770201,914028669,129312892,901303658,8417715,328572459,929840554,384670437,23235767,267469371,467423804,289671680,959476589,468326000,627515745,364935798,262661154,467120693,490252397,924766487,4172248,841968941,202241304,395961705,24037529,857781423,467632628,504409354,490057969,597477316,960695218,622470780,119049854,563620821,17750208,620497501,520909475,782201153,352870115,485673438,921108797,13423603,710669842,716968458,558130289,287197127,526358680,818171345,460982252,400689566,28302417,523310041,326324622,657666094,295710749,733399285,833132862,663611772,85968064,756240864,124956880,497232550,921575951,67924871,737963849,240348718,917141997,915409060,500202890,304472803,968352867,121053634,881412929,564900697,260811092,437899717,354085350,435291613,616838009,85831772,51538376,562554269,272079920,854530977,878982950,319411515,433193683,716666851,931472381,893499415,839008081,624169743,756233584,209623342,59306492,917755992,142899721,828893501,486653218,562907150,907983593,254430547,367240830,141606910,368434072,869072381,108719151,881670907,398748227,257967480,37436714,572100783,806550840,576166594,421159613,116493757,198466413,582899500,118982533,18113930,84100792,230749996,652694868,496177600,577921899,64821112,674220355,497784913,467722657,224548179,645455252,19497945,722920780,814558381,867438420,918529104,251691223,779084018,650273345,392808410,359194570,199584851,846112721,127275060,804178164,353306708,233557401,946615538,1468768,501737168,675784454,661287973,39088986,631570298,937815012,119916282,93290688,66509484,926379726,200592710,605329758,147206867,997630903,777754592,781447033,917782226,583814559,318509970,667817466,51590418,82719094,630871827,729009728,865270939,642392867,296622200,812749291,526833848,421406755,182263479,990610931,904685773,662544629,477848486,403643000,127060127,900809371,143387047,429446995,23107398,818981726,48670190,956097470,303026367,280423132,137952937,440157046,431286785,879686870,619798142,297179575,797637750,97718254,111662179,598513553,403882723,8600941,113084547,88953834,398469726,226673536,859108352,501513283,853411484,243533275,107405390,714599759,549595489,517196454,299977900,584445791,983186537,676947341,878576959,145393141,933614148,382955385,322665636,645135577,148708936,827605891,113606996,72798167,246092557,24101377,344917603,764768946,575026705,590398013,90450282,926951145,67013608,16278628,657456205,856052198,321835464,724820302,173064861,8260789,45622246,121426543,706443551,907161041,314700965,74379841,852462289,115777017,244140537,576239589,500502931,259316018,79994763,940197297,711296053,858783569,130831274,650946168,170547758,298478539,7005581,778682929,351621463,619910675,395543128,76959762,677564440,867246686,636517991,134807608,702177227,862992502,3407854,86722287,547564943,749548184,310233764,801555210,573496839,854765337,522904176,740381086,857640262,242623348,492142761,483859530,499528099,55183770,553665464,408810997,86239826,674272435,225609826,515708627,63873275,569288003,983819036,569939799,994114751,456824975,396295378,982607277,324237687,89771548,695360551,318773683,805074563,386699172,967467982,635682037,969830612,542215154,236979057,117824392,294633810,960638335,459416777,7038652,772980735,4127373,649281307,106516342,11776974,367106494,238326827,501979734,457623922,939295725,383939556,476737035,257860288,235860770,4632675,137914589,234115719,592847929,818504270,614001786,869093467,817616622,727687379,322409188,629981335,1917635,810415318,308960352,874156196,7557045,102698720,273513430,325213430,309214973,858604049,615627350,65638782,177393094,738428822,465215341,33761107,73199697,345134904,121979559,56543806,143975468,374599085,612252238,174706220,677294091,618458337,401397057,827180350,403990350,670004283,150718091,235735624,694282431,526163666,688054694,83286610,224673582,605619826,372907380,97053714,34661703,29647493,69208747,402757802,74901448,236197972,22514326,27112366,996959354,21427362,938377594,192318790,339014795,547544074,605824323,869426234,967980650,662158525,431049499,979566940,764901256,651277228,85200815,391483734,924706577,997264878,68423358,526100270,977063191,841086175,43473602,516388834,965715511,99189351,628112185,799368290,118132976,979016382,101607538,261370379,40880316,466661128,356278030,573420952,372311106,812894831,825440981,442208047,897227309,862191707,783853240,202208913,206071237,341136226,842696539,339057586,59710989,126202483,518772192,13602702,780324510,24385919,477742634,126577152,811856643,910989510,235270038,666134539,890945162,859350850,75188453,410418644,188675544,384005036,577259395,460513197,314238191,738988164,276141747,195159240,626796289,950919266,319781266,205147799,207804358,552413462,634228431,161394687,288658248,313615563,11897603,40013028,129558663,737009561,234015831,61513960,718470091,819250934,632786821,702059181,26477027,56235016,835066388,948128549,660840881,760243261,28271624,5772090,374752515,43466601,984680183,803830477,952182240,278770236,629522345,523102224,128511597,111819053,87611224,101038504,642055598,716087989,792473335,405762651,392296132,339272812,382047077,882097187,327806668,944093099,409025788,401264869,960001703,703982410,344953547,221396107,562693745,468769405,637372639,466491015,644672486,955473087,900944590,61507711,613443148,862977767,110261778,477272641,462834320,463625384,874136150,463622501,825681569,983781847,944904276,364597167,13740878,955164895,809107518,596580800,925336335,51210771,705969397,173484282,260513526,879158896,129052290,609311716,145476847,192977243,461194709,823970718,146796501,897565551,104574060,934603174,180151260,643263128,890713298,109896249,190320523,113879678,360797247,218489779,108162930,561672657,841717634,66470427,62927305,495734320,717649527,60417315,260005330,573338243,336726012,734673839,779725470,693738874,773514333,382374371,294981573,8535066,714933560,510316533,633262591,315412405,146650039,228957295,942045288,351204663,411709085,195259539,165037935,36680199,156297904,526372247,253213336,236928376,620533894,132566626,899719821,951651598,743183308,916966604,115062556,914074970,552988730,919844541,885404412,77762421,75930949,4647034,793289146,232196246,337498501,625973158,1458431,682508278,999448297,903419423,60858071,432361903,414820851,162124595,464298700,660161349,76767172,735671604,14787580,574237655,213736545,322948962,112028365,310550714,40587988,55493148,665435638,29417937,91985505,398113851,333428283,144317358,825777021,440559964,115183739,448808935,169202281,307366717,7220162,528652011,914501238,481845487,216267172,260029080,972504493,384976534,79862174,652236199,22757236,228776286,47310672,374493492,630529265,621042557,884709657,931411949,232323860,334823352,761900502,609728631,64621380,50765434,456619957,98041499,663516444,985779084,945706761,967060680,232608264,819834086,489382828,987800764,918849238,337216067,174072214,551952062,321929572,159009811,801215187,94159797,434217496,537001344,300798845,349682877,604855547,412572109,22223447,433276307,750823350,474133678,600395776,619128557,135387784,70282093,701088357,742223588,966821740,157205909,754826753,187334842,118641570,937021152,809896791,976990229,407792419,939847134,61536031,734912319,492891536,976597651,252184914,132108998,5322035,839086227,144590987,775187261,936492925,521920190,234913913,123192605,116855105,976674955,403949595,985034998,531776663,890919874,79830365,679148827,371730162,431882189,942202241,48651509,642125903,897704124,286086824,45365335,98490660,770114430,222263119,895157478,434280442,801956188,663261722,645128655,32370882,744051083,469275500,553376716,643769233,806885445,111926957,546648683,382351893,710172405,946479387,67683980,191297528,354533537,525519581,600336334,974591932,108825455,166333519,691229086,393696710,463488563,929090672,873326967,103090771,213242224,604830503,346162670,215773545,199069610,130896891,399266018,725051298,907930986,370264698,778653927,864184849,922852482,254766340,568462840,206377,321094592,803381411,201685988,800183928,941658960,300640908,990203012,136737012,331458394,248647640,17708418,272638040,290414160,907941136,540855748,11762532,710336956,564604397,368842864,504210006,80078358,197694815,499553796,487073249,825412157,105246726,941155910,790319215,501668388,312777572,605663326,311033302,561509916,254013294,796920600,136501508,106783469,560918238,692594314,71268658,309438558,675934919,42669581,681088347,964009519,491352865,885957918,436098106,139180331,594131534,917217035,822067657,374304979,964179990,61491668,550829869,143089713,313078907,375233377,180874578,269671941,978795795,689169123,131636921,513574837,915508166,225415207,392230741,594751344,242440401,919341248,223514971,667218994,937511171,455711536,10078928,331291939,391500680,62034352,81785269,968460581,138424254,564625855,729487470,511767567,605492334,732138052,755921232,254890572,863451486,127617354,676188972,17571058,904490745,532192680,292983005,132846111,947551853,912750866,921092919,392056988,821968320,59253089,581738262,574903221,869507494,186233823,148189482,332572032,785692330,47023485,842708877,753443774,565926906,121415157,308057627,734442650,41615594,501103083,401631025,671534654,456364793,104467445,290208516,392144653,940848906,925470281,154957546,621295458,840249470,13358196,965879462,500208739,402776946,603676078,271094518,118243670,898988215,747472860,790001648,813792182,874833709,657099801,160937464,194045875,94339910,727935884,204065429,196280944,358944016,490512489,1165437,846103992,626061688,696403563,461785769,20497903,703850779,73093555,708689957,800779615,215952134,53131286,417305228,114859541,442464090,551069647,878071265,29107249,372241005,634707324,974719819,110738617,108592548,901337933,229972571,471414775,949642,721226143,43060311,598615094,755977241,196233835,360161631,627614971,678122111,502604948,228177385,364494731,439582673,515218009,407991137,984733266,903017880,547554389,572167106,773757854,534769593,446465434,229665198,747847705,647570622,272320958,610689349,31539630,451079179,670487543,37439392,824131351,53576754,107329894,7264978,843401014,294267029,91117362,253662823,556026866,442188765,218649666,500416445,953229463,699578021,334831622,107915814,57866408,336584321,293735427,539395714,95291211,329561193,574645138,826873807,901394512,387917246,757779808,427206346,812203879,97512599,950185888,878799102,376961826,520650932,731836246,125918731,483193131,391283410,498323334,927029816,596258527,158366387,724606254,870527419,148244122,457927934,960879537,218331497,240895934,731288143,710907620,772841079,951896275,560502353,499771129,637800264,63649802,315366008,366855660,317527083,180821186,372312597,837954068,89242428,746880368,569406839,626590619,641707223,510421727,608279571,125568655,41916740,912991542,878188579,60341422,545998170,393619559,314295353,345204829,504230456,423781508,85526435,776233202,188270489,18696592,493987860,75162296,325303014,667369614,174014217,931701552,450209118,79757845,253283765,420628579,781339907,117315544,332360062,370596187,907538609,572540469,606418854,124290516,596597528,206483831,833152643,203092461,816455522,540432502,340717951,48178133,714503568,725891930,211068903,939551524,388186055,980685377,442140514,762200178,558437291,152012447,160635377,411836960,403992439,705114106,830993974,75059508,952250167,420419325,559375223,528944973,543346278,713405880,604402537,388767627,17747746,933623736,544100901,718474181,95012986,302905981,50074208,931107879,209765242,149252498,225834190,991627081,803249647,927590665,78008013,115649821,46819590,710812906,973961459,249883979,115000099,71381593,414558525,841157385,240300072,99548675,224819712,121164511,390417599,979023386,219323766,885575488,451048037,147083949,286253146,693255542,447109419,315702858,378821247,707168621,1489227,845591581,958409668,509432507,14844560,384416868,263490300,163170564,864030507,476310135,672886576,348776308,46030824,545946048,665088752,287250807,74053371,14953362,651525591,964470462,648487278,646172821,401799668,358433908,300040499,282042115,578396454,243710987,799243680,378317775,835249305,727447274,581931747,886343391,826796945,402553456,142446942,454466367,764381437,504613883,425588156,385088313,811048180,1032329,756441483,201793119,453250998,458006055,919354115,232749218,41364317,11331347,112883024,996924067,635380175,545908341,824325781,819373048,183168103,162240970,272729678,37595448,299480896,466729082,705402330,232723801,821202220,68312271,368071199,65233164,157127378,227934814,937076297,589235159,228220996,97464808,353983973,878932021,817952881,84225098,965455869,823332129,505954482,334715432,302594131,251262199,803907169,93661037,55535608,379060858,84838335,96238384,9290853,971017296,159460319,782968555,720198716,954963898,578434586,91616933,60018032,553233381,382221535,873750568,632618190,222383033,970089851,604277733,645691868,908357185,297961772,59120847,945104124,575958856,77190694,263871270,330703835,451676409,118197565,710058636,181847451,233857854,346856746,143690642,675474375,99262583,504417340,624278671,439502833,527852198,149924607,577530496,721940410,369865320,508758822,222617578,617120372,743560841,612691372,112780417,65386796,591736755,115850606,126445791,313082454,434847806,393203279,553306912,618057052,99451003,523708633,228504356,771950456,222602465,156094759,52576457,36733882,851526663,570580011,16739600,608056599,525561898,518579575,278277499,583521105,828879533,44871620,183535821,693005033,177266881,764650578,940120798,573061007,765166432,20144388,57291468,825028820,104952708,294562678,765122811,287006241,465621325,267199607,435488972,638883428,295539396,953061,985710698,150848328,70123814,188376851,451817657,990163985,835315292,43512205,958168033,743240356,875772340,45780420,425351892,709166559,428116263,279814791,650983985,806138077,81309794,567086844,289140300,618507517,434986739,580766563,423427304,574870748,323733783,417613030,638615392,878604216,603501540,485117999,530285181,238880595,12202500,514944544,313853598,717584554,175437526,83452151,273480366,769506782,953962840,140543378,28025993,172419167,893499966,848268738,501725711,483226655,600216209,103134704,158645577,121985290,945843301,114404813,596806604,425456869,680536420,70685596,247333759,203125499,578746610,833815585,253235351,961439550,40535400,112108857,308874689,788923224,868589190,932167671,841820210,642981612,247219758,434594339,635172126,196712445,168730382,966094812,824628895,825864174,905340435,928030628,30015213,600006424,872245503,899773077,699241543,122096817,27299012,838951382,25734719,317682695,648708423,67989542,238932190,86381087,693940993,875561072,996987860,707549126,954185821,386196329,106120269,944912651,298334370,524419423,644355073,63163737,174479650,164299395,508940301,332272906,53248942,247265973,418351266,368267384,422052234,293410797,732811667,546971724,723756108,614509126,599000837,796708901,725960062,356163427,794771978,177328484,445507130,510340468,35538136,81976464,34391299,927418406,477818294,43689703,439388203,394244366,78008367,914578077,418773491,22152018,587274173,275162577,918118226,935999265,814911158,354110518,858290189,635549624,98870390,709785599,887881886,914478646,895120321,164287812,314264820,186541767,674331927,225491870,326200713,77116247,598597697,818090931,109464154,518034446,499207562,755864283,445232376,980495862,197424134,245185523,959450115,816356060,223279737,8608450,593793379,321791822,784307786,399312594,153349061,150270405,946906541,804410317,107618532,1910059,37590555,10222823,602251557,744468766,839801318,71202120,131596617,422142665,458779545,241520085,276954343,967558330,799655804,655413480,883711475,334836251,978693995,125700170,104805698,325754324,810085843,859419899,295232771,289957627,470420524,115937192,788718115,716289521,677632943,871092960,63357121,484222313,508876108,46359733,778952317,584258285,126740489,409577955,884579628,893498193,818469927,36798985,5250559,199315586,970048229,697715357,241292479,746547595,271458322,144751626,534584709,841108762,423093311,610922760,659511013,238493324,945789744,7250892,252152543,942554670,676958418,64748098,240052635,590347379,386928291,316282299,527551546,391833737,364756057,182216392,199219722,358861981,259233891,492664852,668708379,992779680,493123148,781354663,365319636,271375479,899892972,566833161,527478835,524285029,533078762,152977650,557438091,538327223,110010728,759864007,96600587,654385733,790236822,116889237,757352901,487609916,255239838,84092785,889154925,481103580,631938105,677096320,234983365,935967300,484696825,894064704,602402069,333661725,565788336,939952814,897237566,241602528,869595266,306912758,27003612,730657367,846873623,30853092,442831826,643662727,957301328,208914950,890780383,237393844,646698560,647960453,381759634,700515049,844054267,536071965,67616590,206157445,790034082,4405351,819268837,579177473,839900507,590787996,202443622,855858106,561719936,488852140,12967205,482439597,611539354,78166714,280948812,737627178,669865093,313340477,476473073,909396826,591338883,78288265,530877891,463139330,501982582,150985189,429884416,725369782,818240633,832527090,72336356,281391090,581058936,249394443,477303135,182368400,399513109,228437372,793634015,378937166,153430538,726675766,293077251,214849917,62544412,857407679,628568161,666000912,585538398,19279563,909068291,157597010,885610319,243474076,112447797,917493397,378937919,166086209,829657210,230387077,995566176,435626255,591693740,392897501,63568429,533687153,788270599,430317628,416429278,277669773,313909880,663516128,625963003,37804768,877059911,211149747,943791563,783561177,735957013,516689349,721503822,267560323,55591843,176718856,143928991,947965215,270191412,326631726,524195728,972659080,628615174,308664756,555546587,605569131,875381584,127816691,731478637,765056631,115181206,406236804,771451015,418432166,373448615,603655771,722773347,129630528,151866038,994906608,880663692,650354898,615986034,6094898,943692786,477921207,625864847,328559101,705332648,209062074,216009804,22390976,101452563,597167779,53274153,25492319,538633189,164435418,647595215,685655509,414889961,176172718,702405860,410660039,743812593,755941364,593249096,118467098,945132473,697915430,308952096,89902673,751694779,87855352,263635575,457323842,190818459,685734020,379919269,834271552,681243201,419157050,819155768,826310437,22769510,435065404,109910640,18147216,643538594,18481644,821819049,845422686,60253628,656401568,517658737,834138762,596925318,627704489,35167490,502001505,823529119,314776696,992685689,60900058,138037412,150918233,304554924,201076867,152621869,20277765,151475060,73211725,754310922,107697813,541407248,543404797,903956135,136936998,545139449,786459819,61309226,424989400,266235878,417964845,109119156,807598932,218601084,476877349,468634039,509759924,15753363,64756869,741971901,677180556,857759239,94786140,430767484,741729551,105992822,157415991,783686211,896941226,703467089,66866666,132581590,358241191,208529527,62448385,597986959,936330531,147069301,40064210,196795959,217845111,656141020,433595795,32512294,766257498,823316405,241681214,837565799,6056286,649245971,305602768,277816730,636332532,372303264,681094337,857662027,608427703,320255885,946639813,616480115,365674608,942422589,250051629,139715071,430045635,494515290,349743718,272905165,485016741,975925622,694811746,832426283,525556754,432124367,72025662,940481482,192626054,1212127,483339175,698361271,5245773,118877284,810720478,142817178,27550456,124508465,403172586,810746617,434651704,599305681,625254715,811488812,816799765,238178731,953392487,292038742,87981977,682811812,12998363,6112103,439878643,401639927,614129146,655127918,379238235,918529927,620028453,20532905,937624324,417011782,477879913,931836589,926797399,777971880,138439155,22088384,517777535,683293101,512087998,341503788,577860132,967165368,637594411,898845725,500127077,177767359,379228314,751787680,649242459,246576584,362187156,310875294,846331685,512435714,890599306,134494930,96470444,614555979,238975561,667833837,533759237,645281318,243672854,951320927,835068174,185167273,195531386,439003170,365445676,242246112,948893319,629428389,91467379,486926179,855595383,234080347,791329303,505369650,449883665,52320215,463515391,379988868,649516876,770757231,495422713,775437972,855225408,458361463,450245430,335548560,272590898,852603635,698400661,667273503,706160287,441310287,486455449,386487214,700057170,590932855,844110257,477095895,639747945,940574733,405390542,226206041,798875897,639439835,57137257,173666768,180072081,459985322,825156232,98882545,352548193,163076256,426479598,335168478,327003665,539944982,736903899,398616822,196927292,484696617,890568848,977092393,977379120,708453937,335980191,877540752,702709846,431806869,823782648,280871305,227945607,763969179,225266040,32664619,385921548,575821874,69901514,747148045,773286884,854606322,997822718,706622003,611436511,704189482,530245357,924063696,929782146,757512250,18304912,146451619,982058227,686288925,323294438,475992556,630303617,123543915,371849912,297036792,190862447,632061758,253343575,632876671,64684484,318375784,205531942,221644818,93307159,550359003,671695792,17127512,685242642,711263811,316892275,41999943,163900716,605298358,412445645,689721577,33818133,445678523,888953903,604515542,347580437,628884819,900126046,189140585,610014535,427358967,436842801,563345892,46490868,273928124,498019478,469594387,263438162,286887198,612349271,12561273,456896483,450646687,991529087,949243067,272213506,952227232,34950780,947702407,941123228,241032841,677779023,971754451,456901100,528244606,509696344,154185725,534201793,493385422,894426487,240438009,624877256,909986340,554861024,175235094,769123399,745874278,839921385,941684542,730597582,989550775,59491635,734487099,788669937,906561875,188957660,830561354,393949756,214443969,475205895,86772650,39510815,278799360,764504344,629849607,935448786,359966615,497464706,735475971,228772465,983091125,73357857,269889221,542674883,373709772,697954176,753134696,459198832,491520684,766029626,288438995,716576264,201955250,30703068,68862105,19196649,101489849,76349934,165603479,951843619,30018030,647351743,888588899,912344255,736654205,703998480,615042037,965701426,655441334,558875075,712892125,766678262,659667434,719977424,383192901,19629754,352277487,908287808,279426180,562049849,738732637,69445330,522514498,840535303,729407555,316119809,944065763,304094705,701605653,53504294,598504812,49951314,658606999,77115555,941472322,458783336,98214000,853730613,312167084,82609745,940526831,600301628,391288190,785682216,84058909,881327484,69288807,39316084,507944159,562962066,683473158,243338703,984717433,636912649,177890026,500430358,187065254,882643348,917200007,535878061,749134287,3339248,288166314,635615413,204586113,150460922,1442113,53746583,375688741,391726385,353469571,823312195,170923744,175224300,794730063,827368148,412827689,668284144,512134398,328370010,29268927,735058082,440741561,872317224,164725699,438402110,207869913,861217769,240241381,260612685,43735493,623023577,26995867,600487152,361906411,680339951,63598407,37527399,155781353,434634178,304746199,913847076,224762988,167804243,639883590,72876601,209827726,406442508,81234496,94531936,453328150,961721141,330784396,805665136,722524995,250545758,854606586,795238344,425607258,60640696,719402503,664935311,62872989,144371799,947788330,237747442,501674274,411703574,102636162,369584771,881517651,970458282,354046609,931655273,819881612,140668663,986207341,700971219,920968869,809137354,98034452,131034671,567450831,171240290,407467050,120842714,69921292,286578313,508864948,213298682,553720109,120208090,141213959,206557556,72248718,394416380,821564018,499578894,908895335,545692812,349413525,372823777,484916671,294049132,723889777,920621784,270647053,394655425,544226039,467163478,209339892,590329636,88721690,584771390,13077989,758429129,602926158,197585891,816351775,151261742,782943393,90279560,643583647,982708837,883672960,42019715,289187298,408402903,462833487,449625153,647971256,563325655,706367609,423782425,100938454,107998895,99703706,121415591,522373287,614685673,625764041,781796306,138541174,27711579,892040501,734339178,243023915,782021389,833565283,695882000,285811016,497806151,31691145,57129559,251307904,779092526,793267301,658025909,693649091,619036521,381517310,922742875,205580069,30515307,208130272,587599119,648584127,919408895,360458100,960897091,720382997,111712440,88745111,185429559,308804894,408857237,863395506,334245141,633842813,477268971,401152630,14063055,720521371,935375542,276438354,885265795,688488727,581123231,975495439,261682075,837104047,42346432,692374045,309669800,267451919,174108040,6595997,337255582,838200819,941419191,920315688,214037453,292363846,316575386,365518883,118131092,154373416,186735714,786515509,997291056,153891935,684419135,902967191,695624366,457745094,35371304,425514687,504799899,611496843,363684337,704192597,582599162,366169061,308254503,102875357,94767842,123232998,2761678,111344137,341127531,696559674,938059699,84887044,205880409,635878746,335456550,666641053,606969950,589604978,794296566,777013588,212294687,859445320,515462096,215394052,263381700,692435433,548439338,620140842,968992603,490183420,558448626,135498370,426912279,371808526,955967359,263734437,178435251,74092345,522505733,693221948,882495061,572424045,797164333,937954745,320925166,457827345,63258792,979090457,553607485,227336522,471517241,575612057,45495911,731555001,694001310,889308891,921326495,377306595,665711152,217530794,22887564,64693913,476848987,784932483,368198260,407768813,543101092,887532072,123100620,718346857,895540743,787869425,130237151,402939142,975199181,370419741,882472912,200165802,20221590,320413,90213997,896171375,649483214,997978575,178626955,794072757,517444441,172928115,857454414,621064728,109854007,627842876,213554152,759458527,724149168,778217605,120855583,286210575,770743323,261670957,4748890,943656447,660150212,37071260,872366346,783297731,603187385,293060786,292627731,249701865,349177395,344649092,753893285,530923695,439988580,101867439,334559192,617130676,562235100,557278900,10287733,900215349,690056106,6774673,45295820,77635702,93648363,428480846,757888909,906361784,913974095,5066252,42130062,557832171,364673773,153774273,61378970,597176808,205024556,283942904,312702472,490941273,410782115,648060278,59518409,184477717,343581929,145437567,118755439,348828719,133923923,296511805,311845595,121795063,43665406,31028524,450855225,201459959,148798172,179911696,911878274,494846126,467653429,61033183,435007062,922335224,944124300,933420995,638621630,190467704,440067098,67014396,822501122,217100293,22886776,51449997,77168416,36928571,621675970,793063713,383806040,734722339,240359901,105094678,887673890,359152099,485774754,830948231,453740554,96039159,15421347,488541389,878121020,865339534,795269032,941380474,269599069,754036091,783580490,267572026,45262742,314672334,238673555,34469936,101586818,913129339,46659111,161126000,860781711,708370585,728061705,171255329,660227523,395975012,100204631,512053969,124083454,56968719,488532249,931526462,9460204,876837328,972185982,474213098,580702647,349191092,929359640,891883427,241880107,885393156,888582829,810325765,951326728,725544159,601511225,39127077,478787157,354522390,338171952,59762233,548986882,25756840,689470342,106278782,668578417,955991993,677758075,826702837,175385369,354333099,97220340,540177591,351396068,126664204,481961029,803676497,866229096,713752037,979812295,800636869,171325181,834230087,777319524,266215167,862853646,817138709,492359598,833271695,56515778,465887450,237973766,803513026,59234224,703147716,201153371,645446019,71340336,514130704,313525178,640280555,947711346,298382423,539067616,23399066,864552017,444372695,416739177,191174972,235197070,232739941,92467200,111048550,229690607,381918190,863377025,230656396,434064737,324085900,893192508,975789426,907754290,695502320,346980197,71047952,687978688,598832346,112364311,868849264,8264095,894164766,136660456,192265349,233810486,905247839,371769656,302679269,534692918,512293778,652564601,247242356,814398925,689450144,559789574,257512711,836585072,909868195,71186725,872852852,370069485,438171261,415936642,380849687,84916280,258776352,392741467,234083569,52502879,947592083,234391407,724347429,815422938,720167459,429627499,702333057,187060018,1663318,38098215,366572699,4252497,43230237,721120573,623250390,337053242,939461155,16837919,113020385,951045325,290971232,326210583,888496268,502978685,860102781,827990888,141800634,329386046,925916803,10180437,889870055,969896677,652569609,331411812,258722544,842895480,387691679,468663955,12558136,49667855,543983949,693324142,245564550,532800894,925301115,252246809,379399685,691557852,831321000,483439618,239023125,112736916,688770558,229910976,583671257,850495481,626394735,851473551,32431696,204625490,812270161,64030526,64721913,947444987,909632582,258722681,845198039,432095146,580908315,658369521,26285034,538418803,501712141,255155665,669397174,38960432,411425445,723089353,352797498,265199519,179748308,313299805,147403838,806133784,216178765,921656278,270497113,815076070,185324277,893835389,43272158,71181751,203297678,177591769,930075900,45163365,791926742,602087266,337734998,512832365,321683144,105240287,832935637,850839913,765790996,779773301,704655913,572595164,732699141,803230889,819346381,89480903,459962399,439889371,581945423,909174501,942668480,87774372,50088362,607467666,364783202,638442407,473234037,158009949,383425151,421066788,910889051,48844341,26559542,857107465,877838757,623334009,949459197,757226769,515193039,988320347,61546131,904663019,487139573,147141047,38877810,22797491,905342071,162548302,143091308,546907494,644242498,171115712,461168251,586312534,499786502,896174275,343718445,144894685,145998744,813039043,308749840,838069728,92677823,710527086,819657082,661960247,600579869,565695961,534889836,319905888,152186106,138859965,652191113,412480481,275210229,571521743,19065217,39995872,634196349,769676160,298710170,752544151,123843605,527815292,884150534,124166276,655979495,659307345,110412542,863679542,813070899,637132210,720568106,720850687,27738613,198917292,718371912,316640128,99132608,467411162,284219008,865236528,418552259,244368019,104562269,529410415,569073962,326894174,847213392,298899734,436557583,64654260,17422438,761139474,58537986,886377532,46099663,348418052,821778242,952558015,944948298,104474921,61352579,360644693,156503417,478440522,971078886,47119802,668530118,144230700,369316015,866524275,586879618,86327633,2561037,93675919,305657382,402735650,57097853,304382318,240550050,5961627,412817227,492449310,193577632,21535819,175257237,141280800,975449174,484106220,705184704,870050913,729542368,434438253,952296949,59200752,702110303,92705903,620941155,534951312,205649373,47823988,411860916,599599509,121170970,705995434,818109563,777117247,807007853,21754566,142727928,675009353,519067348,886343722,832360062,560064054,368709355,53302821,359831748,378238684,505966868,897392003,482720118,676783438,625847954,44638450,559614925,262649193,266092166,943059486,216961273,40882705,68339542,264888405,38801182,89415764,719676295,764568739,357631303,50065215,218436037,997899714,646188706,668778863,236942043,850235163,546197403,594644943,601642441,451495811,23349204,26521383,8747730,432683623,734023019,578811965,784753423,653704134,72020664,63501518,118124114,475567679,79330466,305754431,679333124,528747616,166829404,81128624,24151370,623623463,164840212,215538454,897367536,71503249,104725848,776693952,489644798,95763260,820837795,178850815,261520483,623216019,906863492,756245863,61491426,546762575,356072512,621268642,389552958,331903981,295177408,152450264,76574755,442181310,93353481,328892857,872318799,191196724,807804356,376194958,516802338,473026298,961507870,248327415,78137784,942205949,903950443,395776623,853826580,570579384,6201611,589734530,31214805,434196345,181516487,113796847,761635208,800404736,357811722,580378632,345921928,464590045,907324401,119830260,795002581,758105811,463887826,197052972,242495308,487658128,272560344,132061135,993867172,590732016,409071409,960995594,21417849,132997672,347353933,909977963,414068785,407053215,253463741,505022986,858931336,466867596,531418412,164762611,58782094,901154816,654313868,582401767,196034943,519372503,720116513,573378077,6216050,39432225,312442299,413180956,163191672,425814085,241814791,935110791,914714169,558588088,538973979,242620585,445705020,541310404,63231336,517637465,476620258,442672896,120009864,311618293,449013996,320695214,887991375,252671553,75621152,447361218,459742779,250724747,567907415,402596637,513684940,618525640,739580000,278689742,69638265,824710818,55260388,841384190,757244413,18757169,364621852,428621673,977284651,61175679,120927196,696831688,67348056,194895223,691451286,187749885,651818330,589567541,165092907,960594603,78918122,817939764,70789101,839458647,961402986,426004252,935962844,409804833,609772302,651116230,881296145,542574234,622564254,690067372,196122335,988169847,325071209,273411695,762836932,315922112,916339578,107033387,904796279,579356746,557974524,964222066,561641578,112351459,91319209,498621705,646783919,728084097,547597673,506662716,500586035,301539877,66789466,982564837,965453676,786474378,513023761,243508422,689701019,481278405,422738233,878556333,591710537,29709749,554018848,53168591,837268941,311731174,553226385,264639763,361863804,171265524,831574888,455567940,951166025,379113907,183454300,677386655,819676416,986906785,926129714,293608320,550592012,292910761,918641203,342760538,18199490,374624065,32091098,922645845,722280506,790891498,382610534,969205820,778754245,757250897,920712335,438032641,440655371,571205541,792604075,248604762,90036450,414127662,42093885,742783910,439713937,573888410,786426771,505871490,294373957,888256258,409592840,341773245,457151568,797398057,216681650,783709885,87808722,65882321,768564351,146910552,666937061,139525465,99831378,119715248,9479544,994863286,152550838,619438326,46708073,629525265,926683733,15071065,482276265,806880655,676916358,712350747,50651382,687231640,928098492,23121814,61271438,582865062,540183067,88926131,80349052,245260157,859318684,534574491,314869767,616467761,512545999,596675654,372063866,952499445,108045955,743157479,482858601,63804994,776194305,682012257,105274291,965967356,829959550,223869585,977744129,400709259,211799021,325742868,617544851,80823384,981928562,654492917,651216085,412075483,910859784,556953872,635488009,210790732,204793752,699787370,351371549,69078440,798645209,57233913,650680513,651467,4766212,441808723,273734713,749349517,473226211,26478367,492799240,779883848,60630626,111682504,940115828,489530217,317484040,250376063,150026368,140343976,617138804,698842396,856084129,65521203,703231557,255763989,510585476,858420298,674807940,635907773,823313339,983129530,511809270,99373233,9606821,193545600,276152573,584133244,379681471,925546438,80423176,905105069,474222982,746823035,605811108,647321729,384143601,965659125,298993496,864931870,593132547,159628055,661645282,601930408,996389886,40313274,880825891,81466197,255289840,776992752,69125457,2902772,542248770,447458100,88038553,633684644,759384813,278216548,706601295,56375733,259634782,787988948,198597987,646780071,17915830,49601386,12796622,910418410,374210573,170476926,462510184,665343995,282152614,288069500,948924740,10037489,196353157,218122838,235952837,404519097,612215455,910999408,756130793,274993583,432341137,420311758,898980301,259957193,118804753,384670539,231971503,855210194,202659765,986584791,809343850,480666852,881785197,172136610,232510339,174008611,837481510,736894710,244177299,839593454,79620588,886867591,692586688,943098476,79287625,147252235,760130879,932445928,430539737,1931594,838002809,908432415,207847313,481379569,768496512,947202704,132549495,611799104,148817670,153109513,626175885,468228895,935934235,721951948,563784486,828005638,596725306,413586452,890417072,219171739,684962768,656893856,994587143,13404153,945300183,369133753,743709066,163446722,210450719,932646202,501577561,140753252,53389595,256715875,122042880,120779853,367921534,844780803,9544282,935431205,64482748,429787548,97309306,242450575,883314244,101025775,73614226,283715710,996241630,50563398,1463130,761484371,58265855,21681953,483847728,301171885,176915216,296667864,432740492,689820302,338584139,899443270,598626235,943224028,41956442,787284478,243472579,880266296,413771267,494614061,862304268,528182320,255834120,541793546,593464342,441139326,908081216,747696661,610962830,125946081,942864581,443181654,80770982,101208148,991273590,157093704,16480965,763166870,773244206,137317176,492340154,299454965,30906765,906440428,88260156,270220393,813715393,731724633,250039040,928131748,582055406,817196557,464610934,258405824,607728312,450493230,205355866,409819133,850112402,630436923,69050563,891642961,702356761,939958215,780990751,484480171,193223151,506224593,934008784,573151696,496397877,778128722,981504071,110007268,494690365,144745596,226217077,777336527,197479519,176041218,285263938,247505862,948176973,681724471,710905930,389932180,617542263,37326868,80424130,714117525,680118170,838113856,627315697,90674934,846183524,169777434,236544953,618794474,962905744,913054194,931180743,286906843,942522786,141084030,170324500,841148627,300125788,922515760,683425558,590809150,557978900,37769498,722750530,100650278,205087088,187434581,1976365,442985359,76608211,649971233,964684389,741969651,993869875,636161337,435491124,675052092,444403143,135500135,18103125,109522579,352499774,703803192,273298846,659162367,821250943,680178310,494381767,253106304,585525199,151949039,242420768,382347995,644658719,517069696,317039841,581679480,941459216,445532216,931960870,513599450,329178857,384153505,925094231,70114715,242471380,440005301,28392217,446621485,911952130,588660271,156012968,32420189,572753832,44927148,762289848,65520981,137973912,438178802,749699651,915477408,855949148,737357761,791245937,44699513,231395697,767573340,670857851,818755007,887676320,399993109,853346431,90649729,422563089,289416194,167512103,24853904,107737010,200191227,300055918,748210670,659977505,281868358,805546202,78106326,413491343,84898687,756069379,390292132,17783164,967367571,741052938,619060013,776347354,106823153,666360735,190632618,709787980,134920775,18217840,683032515,427386390,543236093,216031654,242140279,170158088,546250859,138574866,948478092,93159141,3082702,64343564,30984285,500308930,293708505,86917660,536231660,604126808,49557618,484209268,289628793,238674780,55058511,388899676,89611642,716830547,387743759,343972515,913060459,36476598,467816700,657645233,92583569,712357264,367204023,877496730,110315739,236711521,270819203,933475406,198602238,718226628,229357009,70103898,415175130,467019385,935052488,141837070,148787320,997522132,97124042,862159330,32671579,941371777,123428590,788087706,858423693,524846283,21635083,696103638,70418657,848835858,443376963,861340629,364687176,379038494,63471656,261728411,822894621,595208467,689877143,500932248,32395896,957439959,391402520,352721457,927640657,918223557,765835157,521987228,361621579,188135821,695793741,949925650,799946330,95833021,52848697,317304268,523915353,555363749,827578159,647515272,489537155,434091006,558567561,986955268,386478426,197852185,996987739,705515479,134419044,614033020,39538236,946685529,237345280,184988481,338057889,644694108,111852619,297249917,832392097,305497721,659775448,387885075,217081811,66764871,569196672,596302566,544024791,586777058,510085360,42905274,347413304,114847782,244830577,81818565,528066453,455941098,780381590,190750901,550286714,604218216,438368227,785881979,86970581,864148416,310523051,575655947,635671494,147139480,658036172,73160754,252146394,632187005,210886257,17303849,708476376,358607395,275374283,181293674,516462403,54706047,321531013,902879639,578642971,446459981,138016627,156089807,116831840,231155031,224688594,64947932,451179026,994111003,600853761,81052933,544991311,444188100,609218306,723018624,311538842,261164686,731281712,602821803,945680122,312317585,464596405,14216921,366085008,43059379,789972392,322086590,296022621,680064695,732338109,970795584,373608960,3606892,491491728,279366134,700340374,55775189,903710009,295264610,825075700,538359799,657515560,706148036,235407730,625818914,556563170,865915505,738195394,836958239,739235023,130133666,811150394,571459380,763908854,4362343,303454803,38696043,262806816,413273211,920742879,158407071,615403664,601115474,977674608,25248390,295412271,804825411,848673871,868345101,124731142,998221278,755747560,276447493,245886390,646998480,39243530,288529081,290189441,278572550,454497390,138301351,853500203,734633508,894860931,892665954,508909514,607814375,103975493,50379349,410140303,598544229,919454255,122823620,3270082,273176999,758763485,779996509,161145475,188098036,60741246,616367775,625059875,38801648,890226404,516603379,276606032,762967716,366525153,998125453,145216785,117082503,503585847,327256280,283656571,795271035,182066317,971876491,360543733,252647275,667580806,576034514,348774700,19005168,592278820,636402473,193296582,740379410,829471730,260508364,792401162,133213265,675858190,107590347,882709833,887129755,10831164,650747000,763593407,352116977,712584954,692001137,839161054,47703307,176553927,666934582,97860912,923358029,954538759,23058001,427239856,582427871,427743449,101875765,681515696,704013221,508288955,122518919,886137807,312008882,571192378,778394956,13647968,748131594,123925751,553938045,695112570,445924310,79433787,894786831,1772323,308618759,575453586,175052392,52955954,972489020,124921823,469556042,618973747,680979761,286488264,142895052,543400196,472122059,3369948,804141214,86793127,383667754,203528115,903062781,154721849,954903273,706993858,211731133,977727830,126771966,352654738,13315846,461124434,997363862,230058730,126510510,46309618,729648090,856802838,52940062,705392176,416570592,298229102,902663794,245903350,932045200,930933760,430830856,806822755,851274705,630889199,20980932,25163172,449110501,588149680,164444619,9257844,977761524,693067024,426171040,798706535,87939995,124703985,541793579,386997551,332851472,39789469,874191266,596978535,167617539,442411687,24837495,624929525,640987776,303577880,605262466,16230223,50934792,362557638,888093905,975893263,150954033,906245524,314497344,592583919,321750425,295569829,512440492,177924574,874057172,136239255,555591083,560434825,364828033,598938446,102608433,903543468,998198739,583956009,548376473,711052434,704741261,214060422,471382407,249919244,707698954,531882792,172641261,331266530,318956686,378817268,285788499,473868001,75624662,860858857,650458338,207018467,435866729,545394386,983240106,429797877,625413878,191574059,707222760,118424822,234599741,930849673,372085716,172248748,176751480,692240559,568159314,134274414,330720257,520659541,522022640,163812485,915378519,193921725,509739576,673764527,72113236,619359122,508505023,251985079,275470869,11635998,731163665,559268099,875995552,856842279,715824949,666527349,50451891,481870050,629097513,179906810,829759272,5280886,709021475,137173122,218708223,130078875,97299479,77288186,547914245,384837379,888567736,349636292,614880030,390333424,564294161,804178775,718080854,719795616,829534561,523530403,734981462,507494290,798969793,863044838,90040428,126480839,902134190,727762088,223538282,59006971,385695261,274604981,136536842,55147076,729927984,473035424,114888552,137073389,335474270,171482515,976553909,871518189,413224914,109015200,414915509,605557954,687529745,850403355,18495278,50965687,527304834,894817516,162990049,125082196,455934915,469442487,857938509,167314805,796812290,109113916,719530252,664529107,825736949,914553507,5825501,272431192,108887118,202703560,722647356,159583438,59251010,985270018,186790509,914476496,858985271,580374563,277534245,976553009,856391889,736054807,12829460,876369520,699671514,551663404,119926929,65213395,263343304,47113861,568679731,143504698,259323705,209190172,221469243,437385428,93343293,950641719,950016131,380198272,228507679,620778695,744948317,309680387,90882559,602296096,700057161,590781592,449316663,905630767,365189611,233528951,468456388,464441792,563119877,395340410,171867052,204037749,878546831,432010423,156968854,65610662,852263901,76437195,277694037,514693506,182603804,60980843,348307260,752675676,541405702,310399753,443848686,199654502,223758500,258222181,668724058,463318055,3824941,654252555,906419245,86742544,326497851,421642250,638239228,205888231,767343100,96181465,259674642,664937390,97814742,147378839,740480660,383696833,692258868,875878677,685502732,142134216,286426357,456929172,50710,645261548,911398464,20614044,153843850,83275962,607239137,818863593,210692506,55898086,467251172,890234372,443500133,783975172,458541459,180470908,927641192,134236724,258790918,637552229,189892851,368447315,298668904,851965067,348901451,356330647,310271224,638166852,136948446,383040916,760185153,844629046,606448030,407630126,359672330,639362583,906246540,124551834,132075369,85614363,106555451,23587006,728292303,899432268,413715621,559371739,824894454,639641924,158679786,903957375,157777678,774613748,680373100,473250003,780855580,360144821,138067879,662977102,510992678,259813371,642050624,632489971,214889947,735328622,692740047,373119542,160871732,882266729,29815415,182463663,60136125,390538785,868312841,228032253,427249923,397118871,145173668,978372240,12931179,231455684,775774849,867644784,884900136,985308855,632502546,219216550,83596176,546624894,189551592,75358243,323616949,601467639,454060822,36332494,754870910,929481541,793189887,356928811,980700406,694732917,507547280,542089076,265469758,72182818,995845218,476012786,970309227,143846518,147798660,206477619,83252628,653538108,783610398,415730713,421789700,968947731,736019716,777560092,14474249,396029410,807450395,662601950,293758886,140692549,240175696,511149959,755751491,342515810,407044710,110520206,87231234,949976093,854763253,133373319,779928612,812979174,450015204,761107472,520680372,872129257,300531624,946445402,496498085,669346000,971857592,42908240,397262866,270330339,514094168,846948273,930990573,385686947,927850161,144389991,106057627,99109979,441590628,903179342,320783998,25678994,528596267,770590408,986595846,788123813,110768973,618785840,817794106,563177320,6279842,318605791,130797366,81054412,776870286,158323042,203128261,625167544,346405815,214365688,514042197,973471676,608035686,174077107,841210135,333890744,119943375,194137670,844159897,518416797,482929878,54736111,265290170,555836018,382090076,811802802,6083823,112060330,640765047,500633802,311381268,114807184,562499991,714334643,388758171,6304401,169842413,535668428,727821172,423584492,276267239,363841059,190735604,293190035,317432027,523677219,848012905,496907774,112538082,80408323,448449276,212359340,5606066,879354441,120609811,657509287,955222794,634732364,395567099,479840359,875819228,40848458,138245144,56312801,994915236,232695910,145416761,976090419,524092700,595572553,159598182,952548349,136996905,990469907,327473983,2128667,855241426,934597411,83292519,531007567,849625284,826357863,612836870,410681656,107129512,727390576,421987039,345162079,578709784,214881003,230501745,129812674,504183722,638323170,616701425,937748131,143330962,279804978,840561963,970460753,188555284,155773794,307590065,673084126,728536933,361456315,912532489,398314327,762366190,201117328,832649896,343358220,326022629,24520684,388232920,768345432,555484791,714447406,929460843,445318601,282195790,13728532,393160604,43089609,505069424,846436224,914917618,830471784,36030413,558719993,253912598,459027997,122285555,904451284,223476722,817346629,839387391,556781972,41332003,468229949,160670235,790673944,21147750,888411073,864084898,390459672,538660650,625972445,989475040,141118559,396148334,865743838,354976841,179173899,396625977,96533729,885208396,723783734,285840730,997209349,135147455,178556237,960020400,18222889,122396127,408329819,234510699,788825848,379474405,592871823,72607081,536498871,800174791,788093401,599634489,63584899,810498443,558558580,43033023,347007100,730228095,867528638,287339383,415266556,63153942,571381576,810762095,487769028,781951575,453179963,618625879,69791804,50735722,750228951,14466498,58736931,935078853,584953625,135439409,144964890,616924041,591309371,729763728,652847057,699513054,35909831,93624810,594152066,907793290,557996742,983134923,809470843,467554556,546758319,284541920,997451218,698251022,299774477,312999077,388035636,600076891,909100725,57220317,215151119,475374063,972710001,691465843,77904315,520281182,605393868,77219990,756249142,471106648,910205025,289837594,600509540,383676458,704321312,391407098,429663903,166691438,264322778,122242781,540053735,62726854,983248148,357938349,561114974,851652619,540038856,960139148,659515456,106145403,12834720,757752918,768244694,9864872,28620041,566649315,378041338,484139940,917411675,5436265,172992681,588110107,646824855,416095449,902435289,345882040,1213851,73840934,592008350,592601899,978445354,94274530,776577871,331650009,321637298,334706565,946545040,816608882,177491797,249846496,839528387,986039519,234891934,753791552,968580811,11646217,109935820,648368898,597022386,904621296,578879690,130028920,50684372,448715992,400087858,505330649,941877505,826243076,831095408,779860746,819838959,571283339,952671414,57866713,341710456,549340492,526429169,855396321,390434029,107678749,575503669,16797373,786068832,932441658,358773847,570944331,904436321,971993581,388013138,576458074,25096679,331562650,878232,314016851,106872656,350874009,149374601,130535664,332101261,108873652,976380498,104483159,199808645,666956254,462102216,251076760,834717543,734562997,709782554,43725993,463357077,866689117,62411818,983405390,60242418,822500167,201049608,841963503,903823416,53812412,334593097,393993433,948523308,853104453,171209130,31244577,580069280,796115227,130994310,450629995,710986643,746475571,208434601,407489328,140763991,86396321,364021675,78865069,73761640,52292670,562093067,317613916,640223417,134876627,714695913,18172120,269121544,318208004,680620776,340973241,250891291,12507354,343658428,76651191,372336093,878346271,563187219,527157404,209940084,147359767,626958978,744771064,478072863,234285014,83683925,459895846,468816747,78544564,189022821,778238634,681311408,211007030,692630591,326471128,179530211,149732242,846440657,989423049,60284400,173586572,979701556,879908721,846459183,153305884,779099635,912748264,877361105,978350011,639328376,331329491,22637144,150852267,136326587,461853516,11638085,180282718,59699156,74808899,473705507,846576720,335771665,520327917,597890435,668556732,798553620,665381237,908078908,708906105,345633179,113574318,878084090,244657024,312396941,5354119,378322015,552005916,434075172,499466945,27368492,420744586,938090978,463109550,1470122,878998915,587735270,434885268,229848535,534225370,96665483,159135649,768690806,917734668,139012322,710866496,81670011,178803022,605747179,365845604,521385067,185541309,39503497,155805734,637384223,661183303,72878874,809556528,907662351,150283547,374805557,787459848,43432522},
	748425216,
},
	
{
	[]int{4,14,2},
	6,
},
	
	// 可以有多个 testcase
}

func Test_totalHammingDistance(t *testing.T) {
	ast := assert.New(t)
	
	for _, tc := range tcs {
		fmt.Printf("~~%v~~\n", tc)
		ast.Equal(tc.ans, totalHammingDistance(tc.nums), "输入:%v", tc)
	}
}

func Benchmark_totalHammingDistance(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, tc := range tcs {
			totalHammingDistance(tc.nums)
		}
	}
}