#include using namespace std; typedef long long ll; typedef pair P; #define REP(i,n) for(ll i=0;i v={1,373341033,45596018,834980587,623627864,428937595,442819817,499710224,833655840,83857087,295201906,788488293,671639287,849315549,597398273,813259672,732727656,244038325,122642896,310517972,160030060,483239722,683879839,712910418,384710263,433880730,844360005,513089677,101492974,959253371,957629942,678615452,34035221,56734233,524027922,31729117,102311167,330331487,8332991,832392662,545208507,594075875,318497156,859275605,300738984,767818091,864118508,878131539,316588744,812496962,213689172,584871249,980836133,54096741,417876813,363266670,335481797,730839588,393495668,435793297,760025067,811438469,720976283,650770098,586537547,117371703,566486504,749562308,708205284,932912293,939830261,983699513,206579820,301188781,593164676,770845925,247687458,41047791,266419267,937835947,506268060,6177705,936268003,166873118,443834893,328979964,470135404,954410105,117565665,832761782,39806322,478922755,394880724,821825588,468705875,512554988,232240472,876497899,356048018,895187265,808258749,575505950,68190615,939065335,552199946,694814243,385460530,529769387,640377761,916128300,440133909,362216114,826373774,502324157,457648395,385510728,904737188,78988746,454565719,623828097,686156489,713476044,63602402,570334625,681055904,222059821,477211096,343363294,833792655,461853093,741797144,74731896,930484262,268372735,941222802,677432735,474842829,700451655,400176109,697644778,390377694,790010794,360642718,505712943,946647976,339045014,715797300,251680896,70091750,40517433,12629586,850635539,110877109,571935891,695965747,634938288,69072133,155093216,749696762,963086402,544711799,724471925,334646013,574791029,722417626,377929821,743946412,988034679,405207112,18063742,104121967,638607426,607304611,751377777,35834555,313632531,18058363,656121134,40763559,562910912,495867250,48767038,210864657,659137294,715390025,865854329,324322857,388911184,286059202,636456178,421290700,832276048,726437551,526417714,252522639,386147469,674313019,274769381,226519400,272047186,117153405,712896591,486826649,119444874,338909703,18536028,41814114,245606459,140617938,250512392,57084755,157807456,261113192,40258068,194807105,325341339,884328111,896332013,880836012,737358206,202713771,785454372,399586250,485457499,640827004,546969497,749602473,159788463,159111724,218592929,675932866,314795475,811539323,246883213,696818315,759880589,4302336,353070689,477909706,559289160,79781699,878094972,840903973,367416824,973366814,848259019,462421750,667227759,897917455,81800722,956276337,942686845,420541799,417005912,272641764,941778993,217214373,192220616,267901132,50530621,652678397,354880856,164289049,781023184,105376215,315094878,607856504,733905911,457743498,992735713,35212756,231822660,276036750,734558079,424180850,433186147,308380947,18333316,12935086,351491725,655645460,535812389,521902115,67016984,48682076,64748124,489360447,361275315,786336279,805161272,468129309,645091350,887284732,913004502,358814684,281295633,328970139,395955130,164840186,820902807,761699708,246274415,592331769,913846362,866682684,600130702,903837674,529462989,90612675,526540127,533047427,110008879,674279751,801920753,645226926,676886948,752481486,474034007,457790341,166813684,287671032,188118664,244731384,404032157,269766986,423996017,182948540,356801634,737863144,652014069,206068022,504569410,919894484,593398649,963768176,882517476,702523597,949028249,128957299,171997372,50865043,20937461,690959202,581356488,369182214,993580422,193500140,540665426,365786018,743731625,144980423,979536721,773259009,617053935,247670131,843705280,30419459,985463402,261585206,237885042,111276893,488166208,137660292,720784236,244467770,26368504,792857103,666885724,670313309,905683034,259415897,512017253,826265493,111960112,633652060,918048438,516432938,386972415,996212724,610073831,444094191,72480267,665038087,11584804,301029012,723617861,113763819,778259899,937766095,535448641,593907889,783573565,673298635,599533244,655712590,173350007,868198597,169013813,585161712,697502214,573994984,285943986,675831407,3134056,965907646,401920943,665949756,236277883,612745912,813282113,892454686,901222267,624900982,927122298,686321335,84924870,927606072,506664166,353631992,165913238,566073550,816674343,864877926,171259407,908752311,874007723,803597299,613676466,880336545,282280109,128761001,58852065,474075900,434816091,364856903,149123648,388854780,314693916,423183826,419733481,888483202,238933227,336564048,757103493,100189123,855479832,51370348,403061033,496971759,831753030,251718753,272779384,683379259,488844621,881783783,659478190,445719559,740782647,546525906,985524427,548033568,333772553,331916427,752533273,730387628,93829695,655989476,930661318,334885743,466041862,428105027,888238707,232218076,769865249,730641039,616996159,231721356,326973501,426068899,722403656,742756734,663270261,364187931,350431704,671823672,633125919,226166717,386814657,237594135,451479365,546182474,119366536,465211069,605313606,728508871,249619035,663053607,900453742,48293872,229958401,62402409,69570431,71921532,960467929,537087913,514588945,513856225,415497414,286592050,645469437,102052166,163298189,873938719,617583886,986843080,962390239,580971332,665147020,88900164,89866970,826426395,616059995,443012312,659160562,229855967,687413213,59809521,398599610,325666688,154765991,159186619,210830877,386454418,84493735,974220646,820097297,2191828,481459931,729073424,551556379,926316039,151357011,808637654,218058015,786112034,850407126,84202800,94214098,30019651,121701603,176055335,865461951,553631971,286620803,984061713,888573766,302767023,977070668,110954576,83922475,51568171,60949367,19533020,510592752,615419476,341370469,912573425,286207526,206707897,384156962,414163604,193301813,749570167,366933789,11470970,600191572,391667731,328736286,30645366,215162519,604947226,236199953,718439098,411423177,803407599,632441623,766760224,263006576,757681534,61082578,681666415,947466395,12206799,659767098,933746852,978860867,59215985,161179205,439197472,259779111,511621808,145770512,882749888,943124465,872053396,631078482,166861622,743415395,772287179,602427948,924112080,385643091,794973480,883782693,869723371,805963889,313106351,262132854,400034567,488248149,265769800,791715397,408753255,468381897,415812467,172922144,64404368,281500398,512318142,288791777,955559118,242484726,536413695,205340854,707803527,576699812,218525078,875554190,46283078,833841915,763148293,807722138,788080170,556901372,150896699,253151120,97856807,918256774,771557187,582547026,472709375,911615063,743371401,641382840,446540967,184639537,157247760,775930891,939702814,499082462,19536133,548753627,593243221,563850263,185475971,687419227,396799323,657976136,864535682,433009242,860830935,33107339,517661450,467651311,812398757,202133852,431839017,709549400,99643620,773282878,290471030,61134552,129206504,929147251,837008968,422332597,353775281,469563025,62265336,835064501,851685235,21197005,264793769,326416680,118842991,84257200,763248924,687559609,150907932,401832452,242726978,766752066,959173604,390269102,992293822,744816299,476631694,177284763,702429415,374065901,169855231,629007616,719169602,564737074,475119050,714502830,40993711,820235888,749063595,239329111,612759169,18591377,419142436,442202439,941600951,158013406,637073231,471564060,447222237,701248503,599797734,577221870,69656699,51052704,6544303,10958310,554955500,943192237,192526269,897983911,961628039,240232720,627280533,710239542,70255649,261743865,228474833,776408079,304180483,63607040,953297493,758058902,395529997,156010331,825833840,539880795,234683685,52626619,751843490,116909119,62806842,574857555,353417551,40061330,822203768,681051568,490913702,9322961,766631257,124794668,37844313,163524507,729108319,490867505,47035168,682765157,53842115,817965276,757179922,339238384,909741023,150530547,158444563,140949492,993302799,551621442,137578883,475122706,443869843,605400098,689361523,769596520,801661499,474900284,586624857,349960501,134084537,650564083,877097974,379857427,887890124,159436401,133274277,986182139,729720334,568925901,459461496,499309445,493171177,460958750,380694152,168836226,840160881,141116880,225064950,109618190,842341383,85305729,759273275,97369807,669317759,766247510,829017039,550323884,261274540,918239352,29606025,870793828,293683814,378510746,367270918,481292028,813097823,798448487,230791733,899305835,504040630,162510533,479367951,275282274,806951470,462774647,56473153,184659008,905122161,664034750,109726629,59372704,325795100,486860143,843736533,924723613,880348000,801252478,616515290,776142608,284803450,583439582,274826676,6018349,377403437,244041569,527081707,544763288,708818585,354033051,904309832,589922898,673933870,682858433,945260111,899893421,515264973,911685911,9527148,239480646,524126897,48259065,578214879,118677219,786127243,869205770,923276513,937928886,802186160,12198440,638784295,34200904,758925811,185027790,80918046,120604699,610456697,573601211,208296321,49743354,653691911,490750754,674335312,887877110,875880304,308360096,414636410,886100267,8525751,636257427,558338775,500159951,696213291,97268896,364983542,937928436,641582714,586211304,345265657,994704486,443549763,207259440,302122082,166055224,623250998,239642551,476337075,283167364,211328914,68064804,950202136,187552679,18938709,646784245,598764068,538505481,610424991,864445053,390248689,278395191,686098470,935957187,868529577,329970687,804930040,84992079,474569269,810762228,573258936,756464212,155080225,286966169,283614605,19283401,24257676,871831819,612689791,846988741,617120754,971716517,979541482,297910784,991087897,783825907,214821357,689498189,405026419,946731704,609346370,707669156,457703127,957341187,980735523,649367684,791011898,82098966,234729712,105002711,130614285,291032164,193188049,363211260,58108651,100756444,954947696,346032213,863300806,36876722,622610957,289232396,667938985,734886266,395881057,417188702,183092975,887586469,83334648,797819763,100176902,781587414,841864935,371674670,18247584}; vector u={1,508185981,946619294,302781372,270056996,687842115,520814939,656151748,167551009,76358882,238444764,547320890,936993106,540246320,789064438,326454862,599364945,135586075,395321093,686328970,130745802,374622302,347802839,761381542,379502406,832168612,449421398,967649871,494048718,383712060,444161914,708685504,460197924,121077249,304863638,437892150,913840531,978139963,557112114,254539320,63167040,258767075,638851930,198031160,799287112,257911930,264247202,81678186,30339815,788986595,807417660,61462622,92547631,771688652,737302450,548635935,138628975,751323784,15363444,819908099,201172540,753700332,791891091,161479375,713959795,415626295,64570628,69778276,353790564,934240511,436956075,735008505,720044828,930790685,192362407,371054078,611719282,871831704,949421733,678848446,423644083,671401800,455208564,555552467,86500760,773986301,142748582,305569148,268865485,779782248,679183929,514477900,57648579,808724214,890308841,869864077,21814883,805786198,546311324,731344425,819876469,116093520,193193264,364575396,617843060,24160324,973160674,719135022,952327808,402418776,217902006,616649593,894803383,559193268,69989383,649879708,380705952,647231865,661288209,357958293,79495400,832871520,440069809,510090435,445263480,414378335,146061460,923477955,585335666,535627460,282194932,455409627,96235871,89589377,517956296,867750247,359466865,670586232,677430678,151797309,625767044,905184253,612200631,229376538,715752668,517096657,541235845,853475199,888933942,375559450,72235345,142823080,36055342,338906829,557427128,120677218,16973243,694925455,359713921,251460170,27538317,817282634,634217999,786682132,637396318,359619628,793676874,571277504,982525111,768224271,951975633,301817429,49096452,442232834,300365302,877317302,754713116,141888546,276511804,542904451,706400183,545318581,466010005,716378038,449629280,402228438,893122463,689691582,920096297,296626452,377211807,563081173,715050821,687051763,443943577,421048126,899851600,549344500,161685064,977240315,632272425,740609717,311490471,638125691,644441093,80375190,111915196,179748979,320868644,897084497,978110840,210341130,707514410,765750095,255902659,623455584,99186323,145162446,610048863,712353876,259434518,73218014,755393615,530040119,186711191,49896309,36850383,253486485,572010070,478040010,807987027,161834739,289713359,405350448,487949482,88769119,829197612,870263335,191846196,112896105,121047638,703427520,181688681,7140780,259044796,138299893,811701933,660894836,17398555,315754264,236925172,584799766,32521363,169907228,198263992,177632848,609788580,982717455,921840510,819388070,445468955,986237526,280181451,622077354,645793151,82543880,561928561,589214317,389692459,799702883,838907796,482529459,691932689,737261799,220671069,936759918,194923580,664261660,787659412,33518844,671698386,295450784,28809068,680595810,34533127,389672805,244011856,725044618,746171259,19854266,750243457,82098872,327845581,736492925,604880388,981149822,358801820,110234465,543522623,37415571,307193889,673223679,690093772,672266015,661180201,759921721,36291260,515508483,211341425,172226097,889412629,270527303,594976326,785065650,740021784,487052910,523076510,806025660,773740739,22688550,731331257,894588586,623924804,842138636,777229892,283648891,384413720,297027962,14839770,846640534,744205788,657865317,528771797,324901459,150508567,148291445,314104442,130090156,929953991,117820594,314900522,465101588,688935095,137669980,669761986,44404766,17344042,102841018,954399706,588522223,411534515,970118740,669557667,985197901,465143554,714493541,447012189,708398335,679699223,931351880,139400499,217625366,624414521,515990137,188352902,409306320,892243483,295647737,611034668,212890596,224964707,551858718,882033516,915707219,925085823,280264320,769292579,702811417,154366488,443522111,276235118,633096081,33408570,181885094,933297317,620469184,541809225,269777244,436531179,599361469,7465234,723234549,86941495,445191863,808097248,694959505,303766520,973508214,804452700,519781590,278597952,545377984,879952060,499605364,17695328,93237222,154140834,203618467,4811912,16381366,745336996,800977206,270350515,21238228,234397901,98939561,869234156,248735388,420474788,674256714,158169460,245194590,547024193,996925443,386177393,546439937,36011319,970843772,283553731,48926169,597793402,386968304,863246507,678140929,482521832,65422827,192766681,714742935,495151154,253536944,419138882,495389736,575323279,719727650,87620726,487474577,653645916,493420423,402314407,735820805,33421630,434738004,562482066,992089315,829682396,755479005,622928584,5642672,316386576,902634668,843341534,320023204,844251501,619269475,157333794,167498638,516724007,17473558,700116874,617430080,106712971,356090286,138355617,873233418,426582881,89890802,30974675,158453302,564305657,850262652,957664621,102088479,375573792,636244149,106303294,403118452,649778766,682900921,980345600,878771644,846900234,917551496,115674020,371265992,673147800,19690376,787314790,559545252,426760431,48313674,990374204,308132433,298610734,636833402,308249878,292586656,707569244,779385691,936098146,28196961,711091584,91773943,92143567,279506749,57663976,432091008,865764545,760821082,96011762,241169027,26308095,270082148,578364,942152659,425494060,530941056,26028633,191369232,729665580,538576641,206253917,381322572,130817054,885364932,106707739,937084864,150974901,489687494,187434422,817668979,714130259,525831033,972957353,826142878,110815281,127145157,63406764,733840019,579797103,884832394,914227850,787198422,295577568,459952774,125081299,867292771,610324435,303347371,545206262,127080502,482075393,444574959,691511156,818851394,486314771,622188580,547670036,302397266,188034452,885677445,968566300,772734806,110227271,74090722,463274746,489949501,883405351,122320255,426634443,148351803,990409070,547312540,960781524,758868346,556076798,971500372,571852983,258034874,322216990,408337907,448948773,711751545,764564889,935588670,657871040,849452715,935400290,874597214,124059688,941641787,782780334,355304446,470026285,733582126,731233678,947995421,927892770,80437972,953791498,68020643,624653049,373601880,873181506,382081712,391146082,603407201,155719380,966375769,210494833,161227714,34192879,86916144,738034276,962392168,775279804,63245102,753652898,584893281,621476666,32733233,775681124,560229579,92451317,346507234,201461178,793720350,741601342,90703393,916106665,422939046,854160346,109470970,386867556,284480615,265560234,557028283,704044574,266169053,880994004,497018366,99834634,550690545,95213239,752807346,74627633,730331327,399082111,703341156,60803999,860539442,830285621,188440489,597103044,412294138,221771883,286948893,173205321,560631535,117953101,501127821,840961969,979776313,730311423,597943564,896501173,751356551,264391548,365315982,371043854,313355452,458086537,149803571,829171047,332202306,851598797,860927323,976692738,609279450,997263076,238420725,975054410,436552822,761136887,380428049,275713443,746957273,652689525,69289795,521144307,790442247,343976104,331062923,888748168,466472853,482282626,98985891,448741512,990339076,289785451,648605337,621815256,990218783,936947098,640397870,368178279,821493836,876315570,861747283,579699456,141284134,25624980,531642370,866221441,750666651,118238872,597608834,258067099,68308524,572358329,627212020,296147014,332878872,443157016,938226961,211196699,126748031,195458457,949893014,416241285,235379196,297906019,42250057,453058402,472291683,109434178,476885155,734978120,852499620,470869266,89095328,355835632,32332188,907261291,887927894,882110933,266359173,793963783,803909693,142098326,403530406,709078571,442788897,228426512,93824553,548681779,313141626,991826492,694462860,479029615,769557510,103561614,22188098,206428784,896792630,489556744,378289272,960239639,829257491,204515,457802529,526326842,722764443,496277807,789312615,581176299,521599536,689011282,545193740,957964067,383130637,626895307,987033895,852361661,603215813,309305630,322707469,246870556,599447574,532158728,626387314,838298556,700937784,683017719,523755252,237306838,615151562,418506525,919485457,403144312,467093514,359279113,410834938,732111680,403758143,158606597,287449918,288319063,791509369,368604929,655521444,626697572,267564185,13495094,209875231,228737363,21523236,124385673,664925185,542106704,80440553,144764408,598530068,660533458,82643637,325457067,236290833,587967322,700259059,137983396,491952094,575689639,866920571,210565388,90273869,51827719,857926604,487053470,98122312,339215816,88697497,430609208,542763332,266954309,642968637,903410232,278036051,993188934,177282861,35228652,230204390,616788059,766300975,641074684,174378729,125094056,255100670,935874884,881637993,89435706,335217642,649530258,480619266,323082336,309845459,352497793,763887336,709893408,790747446,349522951,563330000,717481494,421196896,12843502,811564803,793630368,666668395,184286489,996658208,297808984,881569041,428087505,184100680,322002607,402995873,146785439,881571524,661002690,301269274,977459766,499299223,60564204,446326996,296580226,61859529,177254198,147447326,901120505,325771073,158384578,844261387,879228478,857301212,973971218,505407468,374181107,738883394,51220932,666372902,266162091,858257548,651391373,529490503,604241625,621988615,651495671,518961858,935127760,472914485,426158322,185012957,126859812,68686135,695043379,854483604,879466139,553638621,122015045,53511489,459584775,6044486,707467502,642926317,21764354,937247714,237201466,736508676,743778616,609789577,541527794,210335076,10844499,612071328,229206016,848866202,142360472,432387842,342235036,911562756,933915398,997453764,461773889,356022929,754107762,472418556,722426193,717903501,268215566,589026183,919136212,43512942,490372001,376742954,825436425,437064824,91316315,504603198,810500106,718773559,897884143,657237090,337416158,402598662,482295636,860630011,516314373,821694479,627192044,249254916,309147775,429612023,977948258,823932464,877826563,70178542,826540865,329981714,639189773,61677783,394125188}; ll N,K; cin >> N >> K; K=min(K,N-K); ll x=1; if(N<=10000000) cout << C(N,K) << endl; else if(N+1-K>MOD){ for(i=N+1-K;i<=N;i++){ x=x*i%MOD; } x*=finv[K]; x%=MOD; cout << x << endl; } else{ ll p=N/1000000; x=v[p]; for(i=1000000*p+1;i<=N;i++){ x*=i; x%=MOD; } ll q=K/1000000; ll y=u[q]; if(K<=10000000){ x*=finv[K]; x%=MOD; }else{ for(i=1000000*q+1;i<=K;i++){ j=mp(i,MOD-2); y=y*j%MOD; } x*=y; x%=MOD; } q=(N-K)/1000000; y=u[q]; if(N-K<=10000000){ x*=finv[N-K]; x%=MOD; }else{ for(i=1000000*q+1;i<=N-K;i++){ j=mp(i,MOD-2); y=y*j%MOD; } x*=y; x%=MOD; } cout << x << endl; } return 0; }