//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int Nmod = 2e5 + 42, mod = 998244353;

inline int add(int x, int y) {
    return (x + y >= mod ? x + y - mod : x + y);
}

inline int sub(int x, int y) {
    return (x - y < 0 ? x - y + mod : x - y);
}

inline void inc(int &x, int y) {
    x = (x + y >= mod ? x + y - mod : x + y);
}

inline void dec(int &x, int y) {
    x = (x - y < 0 ? x - y + mod : x - y);
}

inline int mul(int x, int y) {
    return ((1ll * x * y) % mod + mod) % mod;
}

inline int binpow(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

inline int inv(int x) {
    return binpow(x, mod - 2);
}

inline int divide(int x, int y) {
    return mul(x, inv(y));
}

int fact[Nmod], factinv[Nmod];

inline void precalc() {
    fact[0] = 1;
    factinv[0] = inv(fact[0]);
    for (int i = 1; i < Nmod; i++) {
        fact[i] = mul(fact[i - 1], i);
        factinv[i] = inv(fact[i]);
    }
}

inline int C(int n, int k) {
    if (k > n) return 0;
    return mul(fact[n], mul(factinv[k], factinv[n - k]));
}

const int max_A = 2e9 + 42, bl = 700000;

int prefac[max_A / bl + 2] = {
        1,951610819,501927483,849317807,191166323,248173708,982424362,232588079,860856448,671154973,499710224,841929891,217507999,265835960,201876905,590816585,214785669,725886624,524126609,422497229,597398273,653258419,572408921,761843085,384818512,63319660,307259936,90009866,526576992,636154562,483239722,37300490,40172755,987922072,958564551,581661214,305993854,38195909,621197845,305755531,101492974,679555362,188808028,148169463,1858960,736977921,37308241,399534933,819215905,328324496,31729117,404191826,493073744,89309784,816774574,64516363,649905009,131052356,901016661,145201372,318497156,344804347,110566178,401448187,40359077,94103993,997822898,615550957,756919022,704881626,812496962,115617183,815021282,686619578,579782990,934524094,861375995,835085648,951286622,851555446,335481797,599834256,245641763,752621075,286164023,397078549,885951502,233136968,918098612,340586847,650770098,92104292,333104526,660756513,331300777,269593491,858022481,242596814,863814074,225867,939830261,897009169,708853823,768353686,29923813,32831957,231588061,644511025,135272165,443754000,41047791,286669969,276979681,806938034,7362571,417547027,771152172,159615066,699888911,282915796,443834893,684069574,197593783,881266060,800048116,629364895,28515366,94969001,173655801,396688048,478922755,795088878,390632053,106661706,413412181,310117544,689071146,331384161,928693088,761553634,356048018,415380550,603655893,828259658,375160961,405818905,214323896,83626382,11597655,946162657,694814243,154293124,555396846,552859048,15019057,177505870,582989351,631968985,980701383,654773554,826373774,363294374,308057484,677072986,372490496,841757416,32004291,377916268,241322250,247232022,623828097,522441793,561649640,929433854,115925492,115907565,425218947,721379529,991716635,915166975,477211096,171803312,212820659,66218457,984614775,552194509,308010402,36046084,532365990,885146105,268372735,747100570,748280238,567238715,887710995,196903079,7073772,205216905,100988948,486062883,390377694,378532990,115403281,503888450,567827302,729394427,882088760,900770609,809196985,356061655,251680896,792885314,306871020,157598515,249490179,616055244,504698718,737789156,853457929,472058015,695965747,469874441,311587357,878760364,405540822,782455383,915495697,592669437,37563575,836675880,724471925,473130092,232957550,412510958,333007835,749411690,590008446,26394406,796671445,311622697,405207112,843402575,988977552,600861665,385892669,17072522,525479491,925560441,277617484,275185042,313632531,844676540,547708338,736465215,535498408,945185707,889316514,743816178,204446673,707357926,210864657,590212585,561525552,239250322,821228911,73829568,189862383,641051666,250187515,132572909,636456178,687430241,909702106,940856078,540440789,139587306,397798371,371406671,381270337,397672969,674313019,947775913,509456888,201423522,966318684,482955274,32567116,467061695,503281057,726331567,119444874,832226681,722145963,668546251,632859338,205703813,773628426,5635587,380138257,986448532,57084755,814459456,536114498,974704864,545023245,258443815,528902040,203253259,669569604,619244846,896332013,597292587,364866697,522968844,459387570,319166486,530316421,247753358,726780130,384282908,640827004,799773091,932126951,185006999,549687820,976103033,872185857,867662278,696437508,880709819,314795475,180807066,89805971,747154114,295898061,441058799,701148374,639191658,185688203,957171010,477909706,145297757,114532351,236255324,529216101,3849298,647310099,130996065,748635378,212604967,848259019,261937763,367924553,734127443,562397423,454054685,114346841,631349364,289941149,280672997,420541799,92862869,823166072,81182741,803704970,442269270,8090,831675488,174714168,22923671,50530621,237981177,591116721,192502013,31357126,958701621,924217172,896598627,31018348,70761259,607856504,823210351,614085592,389890890,817586763,852022418,559584236,507193798,487832784,916015057,734558079,352203960,364805944,991185366,481162304,175201678,254468146,291849770,884294368,565547102,655645460,446126367,420850780,922447581,853009537,460430046,283884744,139054746,106855733,644731239,361275315,341012251,257110521,506187805,596485813,55463513,981930399,514872985,357334986,35159630,358814684,545231467,643868500,599376626,396332115,438202728,541557314,40394770,339640455,291363841,246274415,633882056,694680152,773160168,699500103,383641732,296697449,763095938,337833945,861846129,90612675,712777393,802830021,144992926,236344704,193503980,145107528,855538122,541962510,159226494,676886948,596945711,65753788,482090876,380606083,657787665,770230548,404530929,816071184,6393167,244731384,794402450,410891874,614909923,377684984,15377221,412033053,267539856,152513397,386153091,652014069,146536623,193660195,848445238,10441940,564897051,604125596,86859270,481843872,278876704,702523597,308554702,884794485,496212880,509104842,772578472,387304485,627343629,277896830,677324746,581356488,293300130,538177858,93380082,401984674,483893912,216988792,27370995,407132657,835257153,144980423,87437171,172155857,471497836,802820829,433343609,176106281,409567522,758940975,914514255,985463402,96591329,852592530,876522198,587283246,577307350,455856024,751306221,939806618,261626851,244467770,506782315,731332496,637984558,744842355,478141716,6285377,147685272,924835496,434907088,512017253,386036177,476222250,440842155,604890028,237267936,242366855,178039149,979294232,694551705,996212724,253845281,289235445,748083355,835786784,158914543,288851183,703601722,206029625,202060744,723617861,44532713,959486572,992447147,800576135,496660349,128638019,564326396,94266795,901834121,673298635,125607582,904684853,146288698,972774406,884348235,394283085,484288640,337974759,261337634,697502214,404697295,299174432,197912411,607883363,851890897,94704928,560326046,883520028,71618209,665949756,980253896,137768685,63046607,162620329,18029104,157317951,256802534,911998295,979181129,927122298,667102570,365457908,440989319,412374155,690048406,768668589,996982251,739238802,57415582,566073550,663358060,728556772,498258119,326549798,738659199,64716978,707188146,853945023,291681637,613676466,112384799,797531927,827597661,370248303,533037542,308653660,452245442,71916322,977382479,364856903,748192480,630806417,21152474,573433356,66875096,567900378,159502929,753773333,301478529,238933227,158577764,344355077,950023359,960268965,347584166,481827552,13829735,694093380,493943959,496971759,246228496,900026737,303636779,387016592,216602020,968404926,207973163,447193381,817235376,659478190,798707286,360449440,862110218,372193140,282162992,443773412,275168720,687294533,708227297,331916427,416050314,816679791,310477312,503085651,953921783,278056139,771007869,699287127,239469784,466041862,959553873,217613784,373235197,22753517,243623833,917928671,604174565,701394315,309038759,231721356,916496307,918617007,954810122,660946303,238503495,963103784,822335489,612760233,507506609,350431704,75790069,462569962,598257001,350378112,216810256,518422245,587535591,827056161,241783984,546182474,442439580,458663531,39057611,256667636,75997138,464039832,766939545,855789313,425792269,900453742,666296897,958902297,433168387,439152913,876634467,151191712,512647722,829872466,449902959,537087913,466780944,20660049,124768363,281871512,431465317,109328730,822004328,584459532,647396560,163298189,772176968,758373441,150249526,492245792,369072251,433418091,887086084,501678118,446947266,88900164,46097140,128625385,991833171,444568444,524177144,43908505,809144864,732686070,595914844,687413213,677392501,856505535,883257445,593682394,74984693,785527811,450909401,226316709,87358043,386454418,325698461,526859451,694222462,19371682,264002620,848633697,792316212,282424433,606226090,551556379,421321347,567854358,709443793,311273254,729575642,909075057,377194975,394220873,681483366,84202800,976537103,565857838,857775517,906613099,242555109,567454212,338606248,54954215,527403656,286620803,232989839,983685054,378369010,995350063,658966747,368190929,487980794,772081349,583310650,51568171,111395647,364394020,382281111,328063440,587546203,977524177,651015758,480158153,941971734,286207526,971100743,568479007,267909350,280606414,297496275,465989488,94845925,442312776,909252306,11470970,244067518,41785937,972877063,656087823,463264880,827091129,171724890,507231913,906497853,236199953,607016140,21874873,754960332,675610856,992887653,617679741,530010514,908749844,353186190,757681534,477265408,131196700,227774845,329771568,986338640,37792560,438887376,51949427,913451528,978860867,661727457,921785397,627627168,574761275,235577085,123471668,367276415,805430653,609392098,882749888,135403378,764676482,537678476,538664274,85050758,645817459,208301536,650675936,308289657,602427948,399854226,122457246,545836801,458599137,451306513,202936283,39830894,322770518,488285566,313106351,872773404,813415337,581407847,519658145,520254156,959554435,224703733,20591569,833853541,468381897,987919482,526825098,876282515,179969253,538391322,411753420,499454312,340819315,272904945,955559118,678862812,559823889,498263967,16965043,548415110,887949257,243114169,170958045,986696258,875554190,757116613,62719106,875480677,127003478,903932923,466178261,569268119,12272668,741643066,150896699,560764154,675114778,391075022,125217612,515956797,181366252,152541935,105941911,981641656,911615063,962006723,295015721,54359428,605166278,455010247,259740169,766631009,539598789,627617297,939702814,946845542,614689006,250650840,230157941,203949090,972494096,520345312,43517848,904277376,687419227,698266837,427810475,223649162,282635009,229489740,597572477,489841391,960051373,379625240,517661450,795211755,619284159,961888525,922547157,626243916,971838121,848707117,520984268,69279607,773282878,987643973,384359258,961284901,346771112,627085963,134088395,143272472,414513123,125047208,353775281,703959069,253303129,992436790,656402912,535962057,972563943,853040820,636254864,868020063,326416680,955782170,346707363,158852361,433490648,287382235,678021435,315964822,326189693,590270081,242726978,477931648,991301384,36392350,973395811,648239805,266144751,526766557,919211209,944079479,177284763,98063499,407468436,883718393,51855733,954060265,684764381,312642137,194256847,253348336,475119050,486710915,287066722,825062921,500502656,78279913,666937879,460705431,477812264,703957342,18591377,366233186,173657981,377213633,457967843,532235909,722587713,500166405,681248316,198606629,447222237,88294466,512560867,790786194,732454403,958558474,840824428,23905558,938409154,231116306,10958310,832889800,366039506,511950078,944241793,79391333,71717720,672408492,868093321,132517957,627280533,160135254,484500944,236542985,741557556,964933732,480542196,917767417,35596410,282333264,63607040,611101874,19997707,281179253,983588375,51471616,563804127,11534906,607701910,818171139,234683685,282926702,900552967,392369795,274397653,861830114,517517337,975917163,819869053,482369968,40061330,285355009,112455506,26831972,51991269,630336296,934786222,22419632,442215012,534057713,37844313,425764155,362492290,825823854,736921347,531660978,746673419,741102128,649650998,533273419,817965276,533256534,586082536,194442811,774884612,911509636,559466893,873460481,224709594,15165209,993302799,284181799,320792950,301167961,526252940,21908198,856310131,215554716,357463998,377127099,769596520,529520988,608706956,892719748,221839489,259219303,770454472,803567611,436417672,966845117,877097974,830720687,558473021,38516990,727897980,504313530,494370766,269930233,684960847,316183700,568925901,61695562,305614829,835114190,876808621,852090799,750837047,245015085,443372770,512705369,840160881,648525775,408240304,925576154,210312104,537975758,281150531,666184032,338060455,574059860,97369807,95237957,234710504,32504790,224854739,584610845,197588605,790727223,170064248,987170545,29606025,282306714,377895863,853827021,760676118,323628232,147905845,60315433,217967270,521409645,798448487,924719844,503119497,907467639,529253919,744390132,975676318,424740171,732766199,694178107,806951470,65198623,144010412,399127878,789484878,134732093,282082004,475328229,685227047,151680080,59372704,306731129,499612338,489474424,395851051,532114185,495983082,930383863,645137675,649164505,616515290,567716042,542517498,347643026,275882738,105626741,200050192,679369886,448877017,194547648,244041569,341412279,881104891,624767397,645108650,456899308,830793308,377498034,881249020,379721566,673933870,632453731,705134856,161027793,386350590,276680248,97159599,564305695,97573992,732730485,239480646,428490099,833334137,593821130,584522336,315538394,144113925,110235256,475392745,317407097,923276513,728438809,893833404,629372299,589512887,477570851,571395090,724575347,260737477,271462218,185027790,541060583,635154227,406069053,892345735,188593474,593440479,122868062,177771146,704857438,653691911,875839495,897457477,665119264,140445031,366590755,810743443,24354610,431450710,571417721,886100267,793231198,621277355,266097426,412208982,555172579,520181428,644236258,598356365,159245053,364983542,513835382,15617735,714003961,216264505,900172686,350830865,287825384,337582598,692626125,207259440,783131382,364379250,789002715,611847780,779897975,779809871,518594916,724291290,619728459,211328914,212855363,180424314,322180391,71341341,839421428,240670526,777710319,632046454,387782716,538505481,627865345,667912494,699068264,261890809,867887278,956401237,978864588,206967135,775255452,868529577,121622982,530177004,747850033,753855318,705532089,499740540,490946962,531717493,403920257,756464212,535757054,717490096,982949450,740462510,357468496,687298872,543608930,353984926,789788527,612689791,829210071,661674325,533250832,95589232,186215888,609569702,490865430,54140494,642849953,783825907,679136810,37058828,256057625,129122497,610012445,969525034,52893510,264819293,128007008,457703127,970404353,149613423,284374884,392047058,590663983,637177559,164047367,662340002,926962257,105002711,599413200,162497346,814051599,496923860,524038183,345749320,214549127,93745902,419438022,954947696,73074859,301583949,84084356,118363506,10210384,338004522,934613410,107689716,77636122,734886266,681343294,380998177,806492250,596976612,877030530,242045474,989179697,885439552,35876094,100176902,968019567,489612075,986052386,627013238,171840014,111700697,977604534,397791530,48226729,257091403,542462484,33459166,171684341,344600280,585515315,501920252,196563586,490854492,214014294,207462570,784818398,342759783,289340915,208886611,590182064,220333355,248892948,771962169,11983896,169071470,974632499,930198153,899435141,114988340,16209481,227593418,631306020,858551908,838108988,986083304,559748650,950354082,884555995,95156949,357454591,391540904,867919938,607693202,886668731,823947049,783297148,415011412,145014970,608623429,545006558,669666502,132429255,770580917,90240773,876998489,220825800,79994310,59176844,857016671,234416283,400485924,546347718,157568903,798101785,46339672,269085315,915278073,308615941,700996642,653058610,912725902,630864597,993731675,95798171,11137077,86179384,774001730,185373837,540868212,646807180,841242029,448611216,144114181,938062912,316472951,832441901,656022990,485352328,463589544,396749241,548203895,468331476,472414983,612471692,166871110,799839773,407406652,478807266,371672,328914332,840121163,338970951,181138210,64795739,694139647,948526810,609332645,532110059,639440693,579214205,679130792,931108202,598652400,700965310,495804768,708237473,665361773,532167563,16494713,961465122,405204924,240116092,812976233,695267698,184054301,293079496,128316335,997725835,598620278,895063923,957823464,228601992,868664750,62124478,890996117,332076271,827317012,236115383,566618139,595208155,331261096,722742344,7726203,702775792,12690321,614594999,926816725,454919583,106308542,648333040,966651353,377800117,725941870,9921569,302655853,35001631,260171973,76279111,482975626,885468226,239987162,871873048,344782539,75582806,645511915,769638697,683332437,36595019,25400482,335246207,524254861,442231524,100656675,956821528,207213018,117077127,175015995,858853715,736357838,738886927,328326067,358350905,221522485,117434007,587454767,150525804,628179284,323981678,378997939,324943450,852407361,751302775,214555600,172099144,661112575,27287578,516806360,197563609,597485557,736479974,45611072,738087583,592145738,589954022,435952385,303899878,223550953,818311123,836512944,635271033,220748248,86863318,260286365,645498116,644468717,559279382,4990352,104094389,557495222,96432469,855698592,13460603,635889740,955358631,728709839,59540269,213884596,858806403,710630965,85551627,60295959,780169299,935293971,978816839,651018585,572008104,231035265,715732261,861422209,697143753,255742717,74710132,642557573,729274772,959490120,672640442,908347982,973771946,526577707,455600936,902607470,372318584,320495897,976952355,489916862,461407450,329802169,589610227,239536261,512576276,690717586,190129031,139228842,893515984,145107265,810871501,729681864,66055720,224584218,80084496,53325595,294768119,330551304,99044050,385539402,838411414,488101485,850774418,692977517,482698808,83989421,721217086,696609445,891626739,413449117,309527607,346822321,451857270,550222967,472391712,170433586,199479175,911410266,364494205,990743125,355671503,771085539,756650210,170217641,658027361,463742605,883566784,320528407,494823798,270131980,688259020,969339533,468075625,393797765,974379502,134956334,810807401,718525250,810095747,189978643,700000671,435462653,366261166,838472168,184161963,639418624,454611008,734368293,631817153,836936957,534704632,675325747,339136420,199269834,82788277,500354640,372766535,343942803,671340579,187703348,636676445,142458183,193113355,818966800,186966265,519021894,211838585,632342302,415672009,457317065,890330149,855774633,502055273,242394399,62896849,13748517,989150582,635849004,277167962,446281875,929061731,621618743,972087261,239465834,11469352,380702216,220136597,4072351,954000792,733503103,713264976,520325067,969175204,290097002,509006805,385582847,300612439,655378679,312039344,333677123,236015415,769371128,810665175,467570604,384530546,515497419,683681754,461888755,99342562,19061556,578110558,460759135,501486358,458746048,678289057,968102618,314600785,263027816,635972621,101017655,940913170,132677698,572766775,670567334,242800507,504681601,683068814,661529919,869643698,168684113,612304193,723162156,848754116,188351420,518770796,200334383,307888276,972244592,726214295,711525117,991351349,255757746,872365118,120112342,391920871,655118769,22329802,655234680,661159210,40616288,449391846,582640919,953884584,123396437,445625675,296742316,664091313,439343831,152841613,349472952,931609649,111970589,861902951,695124711,146485505,524258659,763966461,89405617,251059117,523714308,454932496,378053249,90458082,241499141,230628822,51219455,841766662,393136326,712426219,452657660,320877970,567241108,815987455,935693603,599686840,483966932,635630007,686822615,83224707,666860720,213843698,332594309,796236560,934249008,411579410,966447064,122270644,561340472,608798991,761876516,631602770,931580621,254460361,351046432,692264492,758083444,121353692,975216706,238243177,376794570,313941612,271263857,672303954,825767592,607963411,306827447,134214349,644377048,256459272,301407577,931869352,690061976,616696324,855846552,621099272,734277079,406928407,419731248,834850696,484136313,782610187,918624409,498228244,407085135,576814493,454355280,567773433,857956214,323403016,778314436,35227900,578363776,651674849,631160691,923171801,512893291,373570481,713124033,283058535,99430172,177914784,995101902,654736463,140782328,565260905,352143595,298139871,785901468,910261740,169957681,894568243,721539707,4513333,524395875,524078977,594480091,511296356,855726459,657813225,457775900,433134368,33344074,263776273,948174269,91671752,743003918,726773037,959961310,369014425,929915720,274358889,651195520,661238286,286749244,119296348,311644023,313864154,855675102,421553512,351294895,39852092,510609266,563781781,747005207,37469774,851887632,789445273,68247799,248144942,581848334,786912482,648097636,479222719,850237339,263365959,58633673,567256852,398990336,826746257,733752643,758101134,819692491,515131261,860331219,246274744,841039172,810755803,289885059,840109857,802437937,226840893,235764032,640833193,3868310,112831018,804828927,771576896,488546335,695983284,307606670,181234890,556543688,758524022,946140343,189691481,261743840,739471431,214070040,224825122,892018168,911594295,691007580,863267918,747521538,565738539,361061628,168016773,292818128,708858830,4010207,639257569,531062543,392832091,985763754,23954492,890491261,847710937,757489083,248226988,438405823,735869785,591895607,846206717,978837153,256086692,883761196,55720954,456426140,393591192,954086760,294527117,322948960,688455288,221298259,715827718,185544410,735684162,894905874,663389171,522575975,517974131,39357236,348350206,25153172,431664187,187445431,608615734,520544177,87927904,861503512,724388862,94821863,351671482,429871609,854010928,794207998,349411019,636779696,470095759,57067967,588029282,769435612,214038934,220907190,102664774,190697502,862251527,275237632,902815707,801371260,328602704,591632674,640758831,702967851,217793446,48881524,820930469,491818671,528329985,863650217,319113275,257425851,560392116,886017416,492331895,856494148,810776731,436881215,851245679,406059553,745021445,620646924,32414853,971712429,158381165,277575041,701901566,95228746,15618717,699205938,452590319,418386443,121075485,441232102,88450265,883129133,121608478,367379137,888796198,792339367,517871149,752804514,131957921,183537110,235904470,803378954,833916238,38731495,142170105,227576767,609001584,871466073,736616951,796880723,944108311,521777345,570417703,89618173,334074517,733292614,675420088,821249835,111035617,829700051,688395916,361460837,463220732,667894512,815240394,108194083,504004560,146451553,905408332,968970223,631188862,790688128,562023937,463708326,365093839,4364167,55475374,566096763,271804902,343673356,130791271,679825708,387682040,227293638,546541272,572675458,2579345,368514123,149976692,885090764,852940821,525201316,68078690,52643043,578613222,395155000,495343896,177501150,479157651,594211720,896213377,378373418,838508075,104063562,713462587,188123082,905250245,207177515,163449080,148538492,576278589,667882695,688753258,137375338,81281758,27775689,954934402,164509061,60383527,159950056,877356980,669015553,604965275,749407522,522811773,965018775,264876381,997089575,730058397,657931233,513936098,581646439,643268664,43260105,72716021,123524782,674395497,786820812,72946226,456863346,311098702,590244851,924932052,505208715,822851089,832202342,737902799,673101633,298592606,741421859,145905456,82910181,582618747,944950373,574896314,108107067,990959269,799746857,256048423,419840189,854285198,338255090,216797460,432053847,264845245,121346429,274556271,314235855,350727263,71686701,371498584,472019557,809372919,266498613,73086783,544814972,264366966,9332864,636188531,866856895,670125155,475563256,769145776,764760018,65856011,638090741,442482807,213916377,595368427,753448113,641956187,97000577,70089412,130485619,344931238,159017703,434215627,334264220,208655598,512221358,392806864,670635757,150466291,62060125,667636468,426989653,984855674,137677711,301327301,728004834,607113407,509654019,495517464,433956097,739971863,105929170,369735330,177790588,305825900,615226218,898151480,236885580,419377677,75566501,394944667,569414146,642933627,27435025,936893777,159467350,796519020,21482930,293137088,664431465,488363249,282636286,846216704,21487906,822494113,916888519,976903073,89010983,529856089,255491671,797223067,99792215,271733053,956100555,387380996,874688338,608248739,724393052,597540721,707926687,515093569,240610651,684336319,432752025,931797936,573310434,871580904,805652826,806971731,295190789,230992838,303058072,234268429,124505234,80855450,636494646,467037962,357991913,429583289,890444473,812787244,540372974,628071569,904441613,902366655,237669165,940142108,193701478,258744260,211459709,320806122,405984683,810034935,183854261,439479532,233556202,876755669,7627443,701778671,618675556,996749856,111569572,733400791,840184892,159613573,950269469,977156880,444480531,658947267,90592796,276580835,956480484,642644301,341309297,308291820,583948369,774423501,656309177,783800111,453277170,959262565,407325908,452427102,164367857,663176744,317449442,534116765,117308863,658300588,982054509,988865953,545739261,794480643,469444967,822233118,492322498,392542354,140250245,446421417,802891329,853822304,899561229,643440432,546637487,219013828,380253037,873558219,529849206,50060219,309455377,10194901,552687556,753690193,652248841,920194862,258640445,700392600,552153189,522088956,331085012,326523725,85042312,96689273,132550763,77808847,941835486,367319164,576962429,824267679,679554463,257347086,166930358,309911389,281884838,824817752,93420241,549478284,397145952,908158769,14130690,958320775,161604731,83034692,965315497,378523713,653303457,852652243,772473598,516616687,206336563,82570821,445527075,698347114,517180538,312081508,697685332,672351390,628448687,223979079,380006664,301032351,369364667,501485659,537920883,561490344,987656738,707587710,899989757,659751015,926928769,625998124,238518168,258594203,23669909,594117070,771125352,487537032,522709296,318774182,126103140,98437133,821614076,118443362,608682593,10768585,22000952,212317628,258228014,347131143,720386606,428796547,486993716,734214247,721064175,192334950,220257203,369816619,243133892,229411805,628743687,306855473,430873161,436801567,218947800,771458140,554122087,534752398,499174535,706980169,364537661,610264381,518434260,884433310,518910841,601343187,666502761,7070106,458251721,263996939,988107227,284735059,908225326,998165102,540893456,396210284,820599487,428246688,992169289,668251234,516713381,40994082,847858008,963249457,865199236,432575042,851849931,702841977,580799043,549145509,398537376,270697582,608330135,87573992,67865042,272717959,197023936,841107577,360016802,922037029,47099262,760261233,298682490,15818699,473918368,517497653,608673776,70537892,615838757,422866990,387190703,421877385,615677065,56327105,641716346,768595725,753216912,375109582,915981046,410155978,841327602,48183389,99247818,742230116,804905787,510111822,816205405,868014927,95364707,584956171,97843126,244864879,965800541,932552392,760147243,306525910,728260544,923418535,752696614,971526318,742521019,680152182,909325062,916081495,974780111,150259000,403211624,555699882,54586406,849533307,120707208,532238855,789261009,738312341,983905371,466332218,797544366,679836602,995622841,609130880,344581023,515477936,213159919,878698175,643226724,404971191,1307941,419845027,2029894,456073641,253995523,822580738,738167229,951493001,557913914,538099722,175556801,975045228,924953046,130023539,538170453,662780577,74748424,306150985,363976353,769974202,282500117,121484383,834264739,162220205,512725026,117782800,277658890,16059551,110623836,987427406,778266840,867135704,635360170,877725426,726286616,737116351,954388836,726242700,222083472,501060113,966378403,102398602,661064381,444282124,666380376,724603435,789052615,153331482,400628304,920549158,895891353,613046138,997140549,941364537,275671450,118163579,782903688,717603345,375656718,15485289,499025542,291605114,670684599,183748509,984810419,525559768,838670403,831948211,206385584,354200293,532957733,32012415,817989621,531994253,457377046,583597142,423905394,324277305,532391827,344798337,983034943,343587731,456023798,197892806,38680812,261048139,177849843,9881697,572784374,758766516,588605372,334347153,523083863,840965730,307055646,406339412,805230206,88014760,70616472,908649121,194385245,747122022,396855546,267929958,463891906,521105688,780564183,818044924,294520161,463238839,830120939,690958433,896100355,49772266,472239752,69145085,367799462,562331684,809737900,692098284,764932912,865395273,617313254,240246408,357014105,232352394,423704474,255358626,728398757,441263739,896020950,787334545,576432710,395542491,635209584,261556157,291425029,450307285,208473573,187456469,256050276,68839813,473176890,653471993,441592753,340567068,292190579,965530183,625861229,156180549,51989637,975296624,425505135,800585770,855232394,692982965,36606862,893410455,518204801,323511851,146043944,731056293,110651138,501600253,260511614,36337673,741249738,768715071,154882204,852848580,842435659,482820721,654251925,989020953,677066563,194513921,695215979,286634605,729312466,348735113,834470577,937719692,326507558,718801424,619722913,576693091,8364753,358594435,6056167,122091503,402222452,55787578,589359753,491831275
};

int getfact(int x) {
    int cr = 0;
    while((cr + 1) * bl <= x) {
        cr++;
    }
    int cfac = prefac[cr], cval = cr * bl;
    while(cval < x) {
        cval++;
        if(cval % mod != 0) cfac = mul(cfac, cval);
    }
    return cfac;
}

int getC(int n, int k) {
    int am_mod_A = n / mod;
    int am_mod_B = (n - k) / mod + k / mod;
    if(am_mod_A > am_mod_B) return 0;
    return divide(getfact(n), mul(getfact(n - k), getfact(k)));
}

bool check(vector<vector<bool> >& a) {
    int n = len(a), m = len(a[0]);
    kek:
    for(int i1 = 0; i1 < n; i1++)
        for(int i2 = 0; i2 < n; i2++)
            for(int i3 = 0; i3 < n; i3++)
                for(int j1 = 0; j1 < m; j1++)
                    for(int j2 = 0; j2 < m; j2++)
                        for(int j3 = 0; j3 < m; j3++) {
                            int mni = min({i1, i2, i3});
                            int mxi = max({i1, i2, i3});
                            int mnj = min({j1, j2, j3});
                            int mxj = max({j1, j2, j3});
                            int am = (a[mni][mnj] + a[mni][mxj] + a[mxi][mnj] + a[mxi][mxj]);
                            if(am == 3) {
                                a[mni][mnj] = 1;
                                a[mni][mxj] = 1;
                                a[mxi][mnj] = 1;
                                a[mxi][mxj] = 1;
                                goto kek;
                            }
                        }
    bool ok = true;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ok &= (a[i][j]);
    return ok;
}

int get_stupid(int n, int m) {
    int ans = 0;
    int tot = (n * m);
    int mn_am = tot + 1;
    for(int i = 0; i < (1 << tot); i++) {
        vector<vector<bool> > a(n, vector<bool>(m));
        int bits = 0;
        for(int x = 0; x < n; x++)
            for(int y = 0; y < m; y++) {
                a[x][y] = ((i >> (x * m + y)) & 1);
                bits += a[x][y];
            }
        if(check(a)) {
            if(umin(mn_am, bits)) ans = 1;
            else if(mn_am == bits) ans++;
        }
    }
    return ans;
}

void solve() {
//    int cfac = 1;
//    cout << cfac << ',';
//    for(int i = 1; i < max_A; i++) {
//        if(i % mod != 0) cfac = mul(cfac, i);
//        if(i % bl == 0) cout << cfac << ',';
//    }
//    for(int n = 1; n <= 6; n++)
//        for(int m = 1; m <= 6; m++) {
//            cout << n << ' ' << m << ' ' << get_stupid(n, m) << '\n';
//        }
    int n, m;
    cin >> n >> m;
    cout << mul(binpow(n, m - 1), binpow(m, n - 1)) << '\n';
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/