結果
| 問題 | No.262 面白くないビットすごろく |
| ユーザー |
 firiexp
|
| 提出日時 | 2020-04-11 15:52:07 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 34,176 bytes |
| コンパイル時間 | 1,039 ms |
| コンパイル使用メモリ | 107,652 KB |
| 実行使用メモリ | 4,348 KB |
| 最終ジャッジ日時 | 2023-10-19 07:18:46 |
| 合計ジャッジ時間 | 1,352 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 5 ms
4,348 KB |
| testcase_02 | AC | 2 ms
4,348 KB |
| testcase_03 | AC | 5 ms
4,348 KB |
ソースコード
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#pragma GCC target ("sse4")
#define popcnt32 __builtin_popcount
#define popcnt64 __builtin_popcountll
static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
ll v[] = {1,272468856,563649100,860328847,1166232007,1469980682,1783570422,2114790145,2414927516,2724982506,3043866212,3368356714,3696447371,4034088073,4367783000,4668805409,4983291841,5311700055,5632446048,5962746493,6304910373,6633258325,6966338873,7301312879,7647208853,7993963848,8350979267,8692305690,8996693216,9310446866,9642632564,9958899872,10290894339,10635395858,10961388861,11294354943,11631498032,11975500737,12326776476,12683283123,13027785740,13355538914,13693313090,14038027713,14381449601,14738125641,15100567476,15442905449,15798371073,16166060498,16528261375,16906557784,17264332938,17566921170,17880976368,18210846386,18530180413,18861209427,19203828677,19531758542,19866094009,20200842854,20545291667,20893776691,21250418457,21598491427,21923954489,22261218014,22608273828,22950906730,23305273534,23670191814,24010979129,24366015250,24734965862,25096174497,25471796065,25842297747,26164838803,26499153595,26851772374,27187340501,27541187813,27914172354,28248844171,28602397046,28973123644,29329894832,29703616942,30089944778,30427698867,30782140032,31153579736,31510893952,31886182974,32270214646,32632414911,33010343011,33394480827,33782295560,34179892637,34523152775,34832156390,35148796432,35476588679,35795799216,36130194883,36480943054,36798991078,37130838192,37474898933,37816945391,38168327856,38530029323,38863519344,39197471652,39532744146,39877248944,40226443498,40582963016,40939570400,41286912813,41643820417,42009688165,42377640293,42754518130,43106018740,43435219978,43772319823,44117394206,44462028976,44820014965,45179326243,45522928237,45879798982,46246138687,46609701908,46987727319,47357207033,47703142216,48061009294,48425512331,48792273164,49169196783,49544485554,49915842586,50292078218,50675865247,51067373801,51472185050,51804505761,52134752072,52477074082,52818700345,53170975039,53529119448,53879955833,54233065497,54589442905,54952916975,55324780533,55705204302,56058804034,56410699097,56772014039,57133698007,57505226047,57888149231,58255379360,58625752167,59013445746,59392769277,59786991162,60183426398,60525078043,60879847551,61248412940,61610149400,61986287799,62366056429,62731107733,63108690096,63493508847,63885363445,64282614398,64657845640,65029351186,65412717008,65794312624,66187046733,66594902248,66975285229,67372611031,67776921688,68187563034,68606219970,68934810714,69249229138,69563214155,69889053360,70213317069,70548792816,70896440274,71214025117,71548449057,71896995173,72235775351,72587898602,72954789126,73281428742,73611431536,73954116149,74295352127,74647629903,75006086342,75356722003,75709657389,76066476715,76429844397,76801655356,77182126886,77521035394,77854879280,78190494896,78534903935,78884623046,79240902799,79597019778,79944882229,80301624822,80667255480,81035843735,81412578197,81774573184,82126709234,82482422734,82846466951,83219305556,83595802433,83966130352,84337635812,84719748804,85102940644,85495003021,85903678348,86217961301,86551199349,86897380693,87239709626,87589330442,87953309938,88299966376,88651217362,89013582802,89376526789,89746820666,90133132445,90478715504,90830070298,91195948847,91556662143,91928917768,92318023926,92676618595,93049983122,93439998092,93820356302,94218075480,94599746239,94945522504,95303593667,95668008293,96034652099,96411494050,96787038863,97158013922,97534340077,97918157161,98309496002,98713990453,99080204117,99453474470,99843074535,100219967016,100615653808,101016865959,101402921372,101800524148,102204666861,102615505268,103042167188,103367140606,103698858755,104042470507,104384424189,104735939624,105097612720,105445535326,105797766382,106157848850,106520038461,106891489332,107274235133,107625497518,107976680264,108339020461,108701865647,109072273412,109458484061,109821244629,110194551904,110584707099,110961378111,111357125985,111747571294,112090962920,112447517929,112814316419,113177498741,113555672022,113932646967,114299740451,114676919658,115061026450,115452565842,115853066778,116226216308,116596240038,116982898326,117362587875,117756428334,118161596450,118543768613,118941558853,119345552459,119756595296,120178877341,120533828633,120884139647,121249132308,121611143237,121982138043,122370471866,122729992530,123103513707,123494368506,123872887789,124269913992,124661141895,125027893958,125404818570,125789131046,126180932589,126580448550,126970141277,127360339056,127771357210,128168809057,128586646178,128985909917,129354551818,129731274419,130115209628,130506363333,130909206971,131294634763,131687304762,132096591970,132497264357,132915045706,133318905970,133710517905,134111472771,134514011902,134926874071,135350966231,135755141295,136173201237,136597646522,137029535272,137462808125,137759182972,138072373432,138396573406,138718181714,139052375614,139387263292,139722982077,140049262364,140387408077,140732668145,141075526632,141431789682,141790463807,142111020199,142445346067,142798286786,143133469103,143487358382,143857011733,144194746393,144548714742,144916552250,145274865347,145648225021,146037422438,146352334380,146685993086,147032675069,147374206797,147724195504,148088629994,148435095124,148785631119,149149075971,149512054409,149882089846,150268738007,150613169053,150964933688,151331584274,151691599299,152064555992,152454113788,152811415545,153185209653,153575001573,153955534708,154353633349,154726734363,155051645119,155387899956,155736319002,156076627173,156431926045,156798952109,157137575827,157492146179,157862645872,158221107575,158596635939,158975752978,159318255423,159672959626,160041017058,160402984627,160780366868,161158963756,161524770483,161902120281,162286550795,162678433494,163077130750,163436218725,163787963244,164149606192,164511277395,164882870465,165265927541,165632628250,166003338830,166391382684,166770240178,167165011852,167564557338,167926774511,168305223781,168688960027,169077182533,169474740422,169866379992,170257921203,170663002671,171063531653,171478517823,171876516828,172200303917,172534512697,172886010936,173222317218,173576727178,173949104558,174283996068,174637498410,175009281200,175365124328,175739358679,176124540595,176463203203,176817588144,177188326764,177546482883,177922065801,178305570797,178667873929,179046824749,179430231579,179818840477,180216276681,180582802771,180935812837,181292503713,181655909949,182027702531,182408189778,182776411125,183147515364,183532001795,183913175460,184306041773,184711441709,185070714646,185446255978,185833103318,186217776606,186615413487,187009120727,187400891844,187802136889,188204498002,188617425859,189030613453,189371970901,189726804355,190095501438,190457184794,190833065703,191213106972,191577940659,191955578949,192340450187,192731827893,193129137335,193504635163,193876283026,194259404542,194641225561,195033859133,195441963222,195821972488,196219122517,196623510203,197034497965,197452803437,197830778378,198200809867,198587480528,198967163788,199361007593,199766172020,200148332580,200546136023,200950122647,201361154932,201783473449,202170968418,202564213699,202973076904,203374783546,203792708069,204206289209,204617496631,205043511058,205463749728,205901605015,206291552308,206617092652,206954985996,207301105038,207643556190,207999147186,208362812882,208704941082,209059602546,209427975691,209789717168,210166401061,210539932178,210883962839,211241331372,211606934845,211970952249,212349023226,212726029370,213093610490,213471105767,213854589804,214246255316,214647882597,215003148329,215354169177,215716862092,216079823682,216450083172,216836505698,217198961226,217572090834,217963153522,218339524784,218735376221,219130300531,219495115388,219872768869,220257648778,220648995196,221046311026,221435927962,221827039627,222235311161,222634272589,223051245661,223447146764,223792750930,224150935785,224515285202,224881948287,225258661454,225634262498,226005034764,226381324929,226765329947,227156519976,227560780296,227927467940,228300450871,228690056611,229067031511,229462711316,229864119873,230250049627,230647419412,231051557994,231462612055,231888869015,232251736410,232625258768,233016113227,233394644853,233791662873,234189550667,234578074839,234975486856,235379590348,235790901205,236221817282,236597532732,236993951888,237399469289,237808099240,238226943962,238637796475,239048615955,239476745421,239898799642,240337250967,240718182584,241070585786,241427944677,241791561736,242163091985,242543758169,242911954903,243282777192,243668234157,244048564328,244441961634,244846646655,245206435374,245582174037,245968381379,246354023499,246751530394,247144906930,247536205081,247938214498,248340289572,248753689891,249169343989,249531608877,249910104217,250293791186,250682070234,251079618110,251471228540,251862740592,252267865239,252668369149,253083427939,253497943610,253884567692,254282368803,254686441361,255097540306,255525495774,255925051308,256342539975,256766924261,257196764397,257640282068,258008550324,258381856246,258773902383,259149922031,259546407774,259946115862,260332956441,260730619929,261134651243,261545748643,261974620506,262353169362,262748836993,263155014595,263562275526,263980820614,264392085346,264803579556,265232334890,265652863074,266091238420,266499308735,266891020775,267295743209,267696445371,268110983060,268531551868,268939733186,269358344420,269782948626,270214432927,270653190668,271058307147,271476380235,271901042921,272333014057,272777094984,273201385098,273639889437,274084589524,274537163542,274954969328,275256585885,275570833646,275899977510,276220806575,276550885608,276893355677,277221362134,277555010020,277889700156,278235349289,278582404274,278939453583,279288160709,279613361806,279949996554,280297873316,280639051583,280993965973,281359996865,281699656520,282054817240,282424472084,282784011342,283159636287,283532815989,283853991566,284188280466,284542383019,284876998796,285230291483,285601515912,285937742162,286291725643,286660829943,287018460850,287392134685,287780049124,288116736056,288471032567,288843338529,289199247412,289574843642,289959345704,290321127384,290697914218,291082994188,291469877297,291867499733,292225596028,292555622135,292892083193,293237342432,293582727254,293941204916,294299027632,294643670923,295001598892,295366304445,295731181159,296108809336,296477580277,296824482717,297181343624,297546391728,297913802581,298291028752,298665064249,299038337956,299414169438,299797478106,300188731346,300594830153,300940722962,301292706058,301659455418,302019442106,302392909184,302782647624,303139250106,303513296426,303902975032,304283570332,304681623600,305070319063,305438074433,305815602021,306198988159,306590455688,306992282618,307378730113,307771179944,308180942926,308580525059,308998168532,309375584150,309702228342,310040492873,310385420526,310728417888,311084691351,311447641182,311790090574,312144839708,312512898104,312874881380,313252320771,313624690967,313969299744,314326865492,314691888318,315056459071,315434187295,315811536234,316179444874,316556574461,316940220538,317331554514,317733761048,318088540201,318438834135,318802384050,319165667684,319535590021,319922366890,320283900459,320657198038,321049488257,321425133978,321821635044,322215373230,322580679794,322958275691,323342801770,323735019206,324132816437,324521954755,324912661618,325321725972,325720216447,326137829796,326531960462,326878073736,327235768075,327600378151,327967124398,328344168319,328719203507,329090926490,329467154842,329850743236,330242557302,330647207406,331012699805,331385940946,331776265114,332152890057,332548663356,332949302105,333335611784,333733585567,334137527103,334548337509,334975736521,335337160498,335710857866,336101055438,336480827113,336878020255,337275158847,337664009017,338061750962,338465760385,338876971341,339306800513,339683323432,340079884926,340485204509,340894639741,341313816873,341723231862,342134460788,342562364126,342985479341,343423982076,343789429912,344122610962,344457527672,344803514957,345150179777,345507238667,345864465250,346211041716,346568279070,346933020305,347300064350,347677237653,348042442044,348391825412,348748304608,349113030840,349483458997,349859876448,350232133330,350603988850,350984406135,351367456413,351758191745,352167509680,352506179838,352860264736,353228746418,353586441114,353959976604,354349728061,354707032557,355082312075,355470060658,355853133389,356250931829,356636401290,357008103261,357384338707,357767934986,358159725869,358564384537,358947047991,359340597769,359748930020,360151639648,360569937186,360949458593,361301942211,361657515893,362021385491,362394197650,362771180675,363141281442,363512777375,363895119940,364277970856,364670362334,365079193491,365435138349,365810705153,366198335844,366580889061,366978564769,367373822066,367765728401,368164629325,368568273747,368979662887,369401234853,369761246628,370136993397,370523119695,370908873236,371306326316,371699639818,372090932249,372493008264,372895037591,373308529954,373728188040,374111296941,374509101599,374913087888,375324178391,375748638325,376151464705,376566735456,376992499684,377423283509,377862283693,378224220960,378573791593,378937809271,379301166975,379671116421,380058390875,380419190289,380792684686,381184164591,381561054003,381957670005,382350695979,382716541106,383093788053,383478195738,383870119640,384268873005,384657901324,385048519578,385458394038,385856452156,386274690051,386675148092,387042908925,387420387422,387803833108,388195290241,388597147509,388983554864,389376014230,389785718954,390185404192,390603065716,391007973020,391399435954,391799556548,392202572772,392614805711,393039657209,393442810131,393861322106,394285074566,394716718756,395158774397,395517102640,395892667666,396280130332,396663880074,397061465498,397455773322,397847294362,398247899893,398650639743,399063459829,399484449882,399867029816,400264685066,400668724406,401079613911,401502406550,401906744673,402321458969,402747347190,403176725486,403615767698,404011963610,404404188890,404813934876,405213251413,405630767434,406045283138,406456112686,406880295399,407300998595,407738084917,408166458655,408577136610,408997693611,409419836346,409854838905,410293988630,410723904198,411165192284,411607003789,412064701934,412459892513,412787675041,413125434853,413470177564,413813599048,414170300487,414532674883,414875055295,415230531724,415598208178,415960418167,416338754957,416709751898,417054435999,417412997744,417777139873,418142353090,418519948662,418896774625,419265501228,419642241648,420026208319,420417331777,420820252091,421174445522,421523913358,421888019177,422251267533,422621285932,423008592777,423369329089,423742809746,424134311353,424511279122,424907933415,425300867467,425666765428,426043956205,426428353526,426820292310,427219090689,427608146253,427998743258,428408653557,428806725968,429224980146,429617152385,429963863592,430320980018,430685820402,431052903006,431430068739,431804519400,432177395739,432553210740,432936691509,433327999033,433733530012,434097972525,434471270047,434863107905,435238889956,435635177453,436035044250,436421737138,436819529994,437223521918,437634615299,438062734708,438423000365,438796401986,439186369819,439566756993,439964891115,440361162568,440750473367,441148023505,441552087077,441963574824,442391779385,442769590824,443166351690,443571343058,443981552035,444400242354,444808941609,445220703704,445648451420,446072758561,446511151826,446887863691,447240138170,447599345941,447961965780,448333437741,448715363575,449083546035,449453713512,449840189964,450219957229,450613672574,451016138940,451377843528,451753933965,452139310790,452525875722,452923691653,453316542661,453707576621,454110917603,454512303700,454926738270,455339433310,455702958070,456080937029,456465371949,456854519914,457252089173,457642861328,458034042667,458440607830,458840409321,459256482677,459669087958,460056865178,460454459144,460858503477,461269868218,461699656553,462097779607,462516131473,462938986011,463369384418,463814559471,464179262642,464552796690,464943655977,465322055399,465719100268,466117040797,466505438580,466902891538,467306976618,467718323666,468149074299,468525009072,468921314677,469326966506,469735448328,470154279181,470565134403,470976069404,471404162967,471826195769,472264601503,472670820245,473062030890,473468254665,473868179974,474283949228,474703374234,475112937781,475532126702,475955007807,476387578333,476824486461,477231052318,477649605214,478074609345,478505727674,478949396296,479374621143,479813901853,480257549621,480711226772,481137046691,481481680156,481840655254,482204364671,482569846746,482947439062,483323794065,483692977544,484069679499,484453724985,484844914786,485248080048,485616841740,485988588035,486377450536,486755371546,487150637682,487553025941,487937470898,488335220753,488739231350,489150436333,489575733726,489940639767,490314176858,490705646259,491082492471,491479109530,491878183069,492265546930,492663323054,493067305904,493478499445,493907875573,494285702773,494681424791,495087537843,495495281496,495913796787,496324830959,496736570450,497164718363,497585752377,498024185200,498419761392,498791098622,499172368535,499556395751,499946707989,500357443142,500733994162,501129897532,501535793424,501944025241,502362698075,502758835083,503149878702,503558370652,503957121730,504374434052,504792318352,505202589872,505621537289,506044055582,506478515443,506906580542,507293438198,507691103349,508095124201,508506218675,508935069724,509334007506,509752007401,510175605302,510605633736,511049944011,511453769128,511869845667,512295264444,512725373619,513166144224,513591107941,514027271879,514471819850,514921730267,515389888649,515746151976,516120645966,516509586091,516890936346,517288857480,517685071701,518076656879,518473954299,518878102214,519289749375,519714645823,520095012656,520492533268,520896827462,521307331285,521726074118,522133460995,522546285667,522973779777,523399099799,523838389842,524240198445,524630950719,525040300253,525438600325,525856504978,526273017638,526683535170,527103457680,527525826917,527960458550,528393449648,528803353699,529222405933,529645152611,530078026637,530519211692,530948280332,531387366356,531830142929,532286129145,532718052818,533109760393,533507089380,533911179954,534322751540,534749127736,535149690863,535567499478,535991669365,536422408674,536872350337,537270016027,537687311634,538110881857,538541410642,538987738083,539408887646,539846264102,540290279141,540741118155,541201884407,541603610800,542021554402,542445766977,542876951076,543325032609,543744721780,544183093660,544627454221,545079102727,545537031039,545964300682,546403938376,546846436546,547301407375,547758821020,548208765687,548677049045,549136811513,549617229966,549964374392,550277672281,550592584322,550918245602,551242250913,551577299199,551926010993,552243254512,552577704794,552925090775,553264635618,553616341876,553982813022,554309590979,554640297977,554981805974,555324210529,555676647128,556033975615,556385134381,556738921500,557094184963,557457858658,557829972985,558210035836,558550302810,558884634865,559219382831,559563840963,559912363145,560268979550,560626369299,560972971546,561330089610,561695378546,562063150010,562440594632,562803275476,563154351847,563510753765,563874584971,564247426389,564623255946,564994400089,565365797869,565747207366,566131414999,566521828885,566933008719,567246871425,567579851122,567925491786,568267447013,568618071111,568981357189,569328054371,569679357945,570041556993,570404156594,570774912776,571160501132,571507737236,571858247194,572223399213,572585220720,572956553061,573345170049,573704289081,574077826799,574468602741,574847491794,575244570057,575628611714,575973613140,576332482721,576696346495,577062073185,577439508313,577815644715,578185235747,578561935277,578946061755,579336945391,579740475323,580108586103,580480751555,580869843135,581247549746,581642857022,582044949069,582429876053,582827469762,583231514124,583642878785,584068232489,584396611826,584727935288,585071044292,585412682639,585764635647,586125736798,586474043930,586826320685,587185448355,587548125987,587919588726,588301523784,588653612525,589004843649,589367087676,589729513812,590100368528,590485643190,590849466513,591222092439,591611420901,591988736120,592384285778,592776838356,593119490163,593475532637,593842941483,594205217992,594584205659,594960809199,595327558763,595704567660,596088834674,596480632590,596880218803,597253735799,597624161138,598010325386,598390213848,598783770848,599189711161,599571165168,599969170000,600373164701,600783880399,601205178127,601563213807,601912655594,602276789225,602640000928,603010036773,603397357922,603758078748,604131558058,604523043314,604900047733,605296717965,605689622509,606055535834,606432710340,606817108912,607209049460,607607861549,607996922408,608387515686,608797434051,609195499684,609613776225,610014086322,610381871594,610759278122,611142821342,611534193618,611936152792,612322481419,612714947263,613124606207,613524410050,613942070950,614346953732,614738366236,615138531541,615541515935,615953831172,616378579454,616781796472,617200385061,617624104491,618055837482,618494644142,618811719280,619146269506,619492775848,619832855781,620184162678,620549989547,620895126320,621245164498,621609731741,621972254824,622342935994,622730866907,623072645847,623425191203,623792407627,624151612496,624524910690,624917226658,625271673298,625646427375,626034991988,626416648586,626814638241,627194398350,627541178218,627898157835,628263363997,628630920343,629008378139,629381935183,629754754282,630131499547,630514787180,630905954546,631312495869,631675273944,632048750926,632440248323,632817224875,633213883629,633612831737,634000281796,634398003041,634802011556,635213242456,635642733172,635980006757,636333922093,636703471280,637060973981,637434612463,637823298243,638181438445,638556986940,638944611997,639328046749,639725729309,640110461978,640483343578,640859157032,641242635036,641633944666,642039475338,642421663991,642815476756,643223603787,643626997911,644045468191,644434745133,644806778506,645187107110,645569938552,645960717029,646369655949,646748086675,647143563748,647550141597,647956716822,648375252409,648773087377,649163971231,649571082101,649970536938,650387040722,650805719865,651216210240,651634663327,652057494947,652490864964,652911366356,653254667986,653610984478,653978043083,654340820929,654719196150,655096078772,655463076448,655840271968,656224576189,656615911432,657016239714,657389495268,657759658750,658146134026,658525904076,658919619890,659324951012,659706970877,660104803135,660508803182,660919817414,661341860359,661713381400,662085614135,662474707972,662852364121,663247702173,663649754406,664034735323,664432349345,664836377279,665247776668,665673142858,666056469887,666450612654,666858300237,667263109743,667680818409,668092915894,668504407901,668934374372,669352980318,669790325820,670191528127,670564089628,670942265558,671325445931,671716289869,672123851671,672504195165,672899222436,673306256613,673711367646,674129434810,674528754572,674920073842,675325604446,675725875770,676141175724,676561168356,676969973128,677388916803,677812606610,678244658509,678678164008,679062473569,679460277667,679864255700,680275412064,680700568090,681102545215,681518440086,681944051001,682374196306,682814636496,683222796403,683637673925,684063382255,684492287082,684931492095,685358688850,685793112805,686238800343,686688081834,687151958521,687481139203,687812631750,688156163565,688498052941,688849652255,689211343502,689559265892,689911535279,690271265396,690633746282,691005135593,691387675852,691739036991,692090271191,692452546881,692815473721,693185927451,693572016540,693934884550,694308398049,694698010808,695074792956,695470517830,695861454783,696204766375,696561122856,696928134215,697290992240,697669335632,698046236609,698413261424,698790443109,699174717779,699566093251,699966479693,700339739044,700709823543,701096333492,701476114233,701869844140,702275134877,702657186657,703054998548,703459014946,703870054605,704292108860,704647732706,704997855662,705362572698,705724983246,706095694277,706483779223,706843614895,707217077730,707608109375,707986281273,708383228428,708774850992,709141525004,709518372333,709902766909,710294474152,710693865398,711083438845,711473757901,711884474135,712282057557,712700171442,713099812794,713468162786,713844885121,714228648026,714619883261,715022516642,715408154703,715800888416,716210181941,716610614309,717028460170,717432489725,717824036379,718224852507,718627498906,719040292107,719464426290,719868450949,720286559106,720710847860,721142705765,721580806772,721918806699,722273251364,722644633790,723002026267,723377336004,723761306174,724123504132,724501658298,724885629032,725273620348,725671199568,726051331129,726422583615,726803561592,727187482745,727577976530,727988412840,728365291154,728761045579,729166981354,729575153362,729993764865,730375895797,730747568720,731130678463,731512464850,731905144965,732313170702,732693287993,733090432253,733494813784,733905748702,734324108109,734717019390,735109163321,735519189936,735917871398,736335089691,736749758874,737160661600,737583427613,738004906141,738441229522,738856174302,739223609714,739600927269,739984698792,740376345601,740777465961,741164718224,741557051266,741966794834,742365961900,742783307821,743188874590,743580598436,743979991572,744383356533,744795165468,745220377148,745622885657,746041140776,746465205389,746896572050,747341747230,747720872292,748117943188,748522525321,748933922639,749351708985,749759697502,750172097793,750599629955,751024347007,751463306778,751880872432,752292435373,752720302619,753141880458,753580360109,754012739492,754444633027,754891381148,755336643853,755796796009,756166419406,756517676961,756879947881,757242843585,757613224286,757999459349,758362211186,758735424501,759125818601,759502441938,759898210819,760293710398,760658121328,761035892927,761420952602,761811682354,762209023794,762598901987,762989904072,763398070845,763796995650,764213815204,764617557232,764984543942,765361722530,765746055984,766137370648,766537676057,766926219065,767317734941,767728469239,768126681142,768543759538,768950249380,769342102036,769740786111,770144544094,770555585864,770981663499,771383308571,771801069085,772225415477,772656417793,773102984407,773459300656,773834660178,774222391612,774605120671,775002837011,775397873618,775789708589,776188881492,776592421689,777003979124,777427173616,777808469461,778206272362,778610252894,779020939116,779441824544,779847611133,780261406507,780688157115,781115568136,781555204200,781954726787,782345447050,782756848675,783154062627,783571696993,783986616204,784397490184,784819265983,785241482314,785677079533,786108175801,786519107873,786937469003,787360097555,787794369346,788234164601,788665127917,789103912328,789546215920,790004251744,790422169791,790792885424,791169191981,791553252818,791944406391,792348616898,792732190565,793125745635,793534166666,793936199809,794354207463,794756728906,795148075630,795550462220,795952286337,796365990188,796788895388,797194369610,797612465334,798037198887,798469038921,798907709237,799289399447,799687356918,800091304255,800502117783,800923732951,801328972319,801743227036,802169596528,802597656888,803037106708,803449706202,803862443625,804289818583,804714759389,805153948274,805584580099,806016345293,806462750916,806912321584,807371886246,807765161324,808158770188,808567159262,808969241060,809387303477,809800999862,810211805541,810638544883,811058624008,811496355429,811921057876,812331967883,812756245695,813176851351,813614103313,814049923628,814480115181,814925000879,815366581984,815823723357,816254195533,816665287720,817093384796,817513331061,817950499985,818384553332,818815284449,819265588832,819704108373,820162741412,820602171717,821033071135,821480220758,821927081237,822387103092,822833188399,823291446296,823753887272,824225443064,824682389702,825002406262,825336664996,825688098649,826024354516,826378750356,826746806109,827085965369,827438839894,827806265541,828165340384,828538638817,828930392300,829265121436,829618514685,829989997557,830346115282,830720144582,831107748747,831467379610,831843071698,832229503850,832614810573,833012364707,833385182994,833736154186,834092500400,834456466214,834829059133,835205045601,835576293417,835947648405,836329001352,836713379215,837103543758,837514540685,837869849205,838244378913,838633219127,839014628312,839412606178,839808753739,840200563740,840597829493,841001974696,841413439586,841835193780,842172566043,842526985416,842898746380,843255710591,843630833308,844015128001,844377113023,844754556333,845139162413,845526512265,845924301194,846304666105,846676402847,847056962704,847440316457,847830932678,848240782396,848618287413,849013979593,849420121421,849827622308,850246151856,850629346045,851000862079,851383818991,851765990426,852158442536,852567187068,852946045846,853343069725,853747688137,854158852380,854576859776,854970850502,855361923865,855773169362,856170680213,856588039158,857002925005,857413905805,857835953013,858257837778,858693602005,859102581348,859448191066,859806361441,860170710178,860537366735,860914134590,861289710925,861660536604,862036785630,862420769138,862811992366,863216289474,863582897550,863955921348,864345547592,864722519533,865118183262,865519592653,865905574594,866302909929,866707040528,867118060161,867544389704,867907177426,868280712714,868671555089,869050133827,869447143816,869845011459,870233585965,870630966941,871035094970,871446393635,871877377915,872252989167,872649460782,873054931794,873463619464,873882468917,874293323683,874704090728,875132241129,875554302728,875992771661,876385953970,876757433560,877139429197,877522802074,877914541507,878324768992,878701185752,879097746098,879503038972,879912442888,880331586089,880726445725,881117063341,881526923742,881924987388,882343219476,882758961035,883169665968,883590032966,884012143117,884447043197,884873137193,885261124468,885658701687,886062792258,886474307565,886904290352,887302123590,887720236940,888143280200,888573665350,889019150173,889421408978,889838183538,890263656122,890693026294,891135486516,891559165826,891996345815,892439997159,892890241589,893357076781,893692061855,894045653774,894417665466,894773301921,895147683754,895534897170,895894981736,896270721715,896656828737,897042618034,897440059694,897822674154,898195333951,898573156269,898956528245,899347259018,899754550956,900135304724,900529957294,900937436114,901342249519,901760199509,902147625629,902518966064,902900291363,903284534680,903674751149,904085632388,904461959210,904858018617,905263873833,905672137367,906090855432,906486869570,906877843100,907286546765,907685190026,908102558732,908520312270,908930597650,909349687556,909772129132,910206629748,910628351787,910993978876,911371577766,911755883600,912147946301,912546500343,912935197816,913325959871,913735370979,914133619903,914551550925,914960862660,915350463714,915747908991,916152060532,916563592891,916991610209,917391126900,917808707287,918232550082,918663363469,919112044954,919489944535,919885714570,920291660616,920699835678,921118285558,921529197170,921941106979,922368908269,922790149282,923228594605,923648457879,924059753965,924490741365,924908557081,925346212987,925779513448,926210825894,926659221254,927101005980,927560339376,927953326671,928324426778,928708929555,929090084628,929482964507,929890215788,930270736126,930668850692,931072771711,931483231506,931903018314,932294263359,932686617460,933096349589,933495757285,933913308351,934327743215,934738659715,935162943841,935583558606,936020823191,936441420445,936832250268,937229619734,937633721709,938045542316,938472256198,938872494293,939290376882,939714206628,940145131973,940594928117,940992532852,941410256794,941833492114,942263956316,942709938290,943131417526,943568922441,944012581889,944463451804,944923194197,945303774069,945701829433,946105733139,946516246785,946936098999,947342882416,947755839267,948183340778,948609286489,949049124016,949464077559,949875656530,950303402824,950726958682,951165540848,951597756820,952028704023,952475956768,952922640513,953382717840,953795945236,954209928426,954636556054,955064181066,955503787985,955931841037,956365519301,956811050770,957260544932,957723191654,958148043412,958586212635,959028881135,959479472149,959946162612,960388044820,960847472586,961310898488,961786926704,962209863199,962557180887,962914103801,963279921820,963647875815,964024768740,964397663566,964770214719,965148557266,965531663221,965922590824,966330252636,966691377997,967064911245,967455752662,967834326487,968231336754,968629207861,969017773865,969415159722,969819285239,970230595632,970661562733,971016196875,971390899993,971779514592,972161136306,972559143829,972954996960,973347373580,973744657012,974148842453,974559938585,974984582019,975365006125,975763287764,976167131474,976577472175,976996777124,977403849004,977816739031,978244422268,978669818586,979109454076,979495535605,979866439343,980251382282,980632158312,981025204065,981432355954,981812882713,982210942474,982614888897,983025485067,983445676163,983836311144,984228763218,984638498788,985038134994,985455796533,985870025629,986281071494,986705404745,987126039101,987563621527,987983393422,988374849517,988772143338,989176344142,989588068311,990014429317,990414867206,990832716217,991256821463,991687547224,992137825273,992535096437,992952552801,993375995680,993806560489,994252783159,994673968319,995111414744,995555297507,996006161642,996463258969,996822842586,997198486019,997584975853,997970187874,998367757387,998761263169,999152819172,999554552659,999956784736};
int main() {
ll nxt = 20000000;
ll n;
cin >> n;
ll start = 1, a = 1;
for (int i = size(v)-1; i >= 0; --i) {
if(v[i] < n){
start = i*nxt+1;
a = v[i];
break;
}
}
for (ll i = start; ; ++i, a += popcnt64(a)) {
if(n < a){
puts("-1");
return 0;
}else if(n == a){
cout << i << "\n";
return 0;
}
}
return 0;
}