四川NOIP2020选手数据.rar

#include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> using namespace std; template <typename T> inline void read(T&x){ x=0; char temp=getchar(); bool f=false; while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();} while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();} if(f) x=-x; } template <typename T> void print(T x){ if(x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); } typedef long long ll; const int MAXN = (1<<20)+5; const ll mod = 1e9+7; const ll base = 1123; //basic int n; char str[MAXN]; ll table[MAXN]={0,0,0,1,2,6,7,16,16,30,30,49,46,76,67,102,96,138,123,179,156,224,200,270,237,333,288,385,342,453,393,531,453,603,523,675,591,779,665,853,744,961,822,1069,906,1168,1015,1272,1094,1409,1201,1523,1311,1649,1407,1787,1529,1933,1658,2057,1758,2242,1892,2364,2035,2533,2172,2709,2304,2862,2454,3044,2590,3262,2749,3408,2921,3601,3078,3807,3234,4022,3434,4202,3576,4455,3782,4635,3961,4865,4132,5131,4348,5347,4551,5549,4736,5847,4947,6060,5178,6343,5379,6601,5583,6854,5865,7104,6049,7425,6287,7687,6537,7999,6764,8287,7018,8561,7294,8825,7521,9239,7817,9486,8071,9786,8330,10162,8603,10472,8895,10802,9145,11191,9459,11469,9790,11847,10054,12195,10330,12588,10676,12894,10945,13364,11309,13670,11639,14041,11915,14475,12242,14842,12613,15236,12939,15710,13281,16024,13610,16496,13976,16943,14312,17312,14734,17700,15023,18247,15429,18653,15839,19082,16160,19520,16576,20003,16989,20387,17299,21004,17737,21422,18143,21896,18540,22384,18938,22820,19413,23328,19777,23917,20210,24303,20682,24857,21070,25411,21493,25963,21983,26399,22369,27009,22859,27441,23318,28018,23762,28696,24248,29173,24716,29635,25135,30349,25673,30801,26127,31439,26617,32011,27061,32614,27696,33149,28090,33810,28588,34348,29174,34978,29624,35628,30172,36184,30693,36766,31141,37609,31735,38122,32288,38729,32836,39393,33358,40003,33923,40629,34401,41464,35034,41986,35647,42700,36150,43348,36708,44074,37376,44658,37833,45493,38499,46125,39089,46773,39590,47611,40208,48294,40918,48924,41488,49767,42090,50321,42707,51230,43333,51938,43897,52577,44616,53309,45194,54276,45891,54960,46543,55666,47089,56484,47778,57224,48528,57906,49082,58922,49849,59548,50478,60360,51147,61234,51795,62047,52533,62821,53125,63800,53843,64426,54689,65286,55280,66084,55954,67010,56750,67792,57388,68802,58227,69504,58906,70344,59594,71382,60344,72129,61121,72873,61774,74047,62588,74758,63310,75728,64058,76686,64835,77536,65726,78338,66330,79339,67088,80245,68003,81265,68722,82153,69504,82991,70382,83811,71007,85136,71949,85867,72745,86902,73567,87858,74299,88775,75202,89721,75966,90819,76776,91645,77710,92665,78479,93817,79325,94834,80243,95660,80910,96855,81973,97717,82827,98680,83553,99866,84473,100923,85414,101775,86184,103087,87111,103881,88040,105143,88907,106151,89753,107081,90821,108151,91627,109441,92561,110393,93481,111389,94316,112551,95275,113671,96261,114661,97033,116190,98105,117032,99038,118143,99988,119275,100906,120271,101943,121387,102763,122822,103797,123798,104887,124918,105743,126036,106619,127319,107877,128433,108691,129706,109749,130642,110678,131942,111621,133357,112712,134399,113710,135381,114713,136897,115755,137811,116809,139163,117763,140529,118789,141680,120005,142758,120819,144247,121981,145373,123035,146579,124002,147793,125090,149096,126280,150160,127115,151887,128377,152873,129497,154175,130539,155547,131562,156712,132672,158052,133666,159461,134780,160561,136118,162005,137177,163291,138173,164620,139377,165706,140254,167493,141621,168653,142773,169906,143724,171440,144948,172747,146242,173913,147246,175443,148424,176633,149566,178223,150702,179641,151800,180820,153237,182098,154202,183852,155478,185091,156732,186586,157866,187950,159044,189284,160263,190448,161343,192443,162703,193525,163832,195009,165044,196665,166250,197898,167528,199402,168673,201124,170015,202272,171333,203698,172374,205212,173601,206986,175183,208256,176165,209869,177507,211057,178888,212608,179989,214316,181267,215765,182609,217147,183845,219146,185227,220349,186455,221983,187743,223485,188969,224909,190597,226327,191621,228198,193040,229588,194362,231150,195534,232870,197098,234342,198414,235740,199510,237875,201019,239223,202419,240720,203738,242332,204950,243883,206521,245467,207741,247421,209157,248647,210616,250571,211938,252119,213174,253760,214788,255168,215969,257242,217595,258568,219015,260144,220243,262332,221791,263839,223228,265211,224466,267093,226004,268561,227468,270540,228858,272148,230142,273801,231852,275397,233032,277515,234638,279163,236296,280813,237517,282451,238959,284137,240557,285759,241785,288080,243433,289402,244928,291154,246503,293100,247951,294628,249426,296290,250772,298652,252430,299998,254162,301884,255471,303582,256929,305576,258633,307174,259885,309317,261604,310921,263114,312733,264539,314821,266081,316378,267921,318036,269276,320238,270914,321660,272368,323844,273921,325858,275505,327746,277398,329376,278738,331450,280276,333092,281952,334951,283384,337045,285236,338799,286817,340353,288072,343100,290082,344651,291613,346401,293169,348447,294684,350474,296596,352341,298044,354459,299634,355925,301539,358103,303096,360135,304644,362088,306544,363932,307928,366207,309770,367773,311414,369816,313020,372102,314694,373955,316433,375709,317965,378379,319821,379893,321532,382249,323178,384157,324816,385933,326875,387777,328284,390221,330057,392317,331937,394183,333383,396273,335218,398228,337154,399998,338572,402744,340588,404462,342422,406810,344236,408858,345808,410631,347548,412589,349170,415359,351183,416981,353065,419019,354556,421321,356364,423686,358488,425470,359972,427804,362058,429712,363800,431772,365366,434334,367250,436407,369164,438309,370822,441011,372796,442675,374852,445149,376544,447207,378188,449170,380437,451340,381977,453919,383882,455837,385740,458155,387636,460337,389474,462507,391576,464399,393041,467666,395321,469362,397075,471402,398904,473808,400889,476001,402849,478229,404585,480687,406435,482593,408721,484979,410380,487407,412234,489672,414484,491632,415991,494559,418269,496377,420139,498768,421981,501390,423997,503506,426083,505572,428037,508252,429939,510006,431768,512804,433746,515449,435726,517642,438030,519686,439579,522393,441725,524515,443971,526798,445706,529068,447676,531630,450017,533644,451645,536916,454001,538904,456151,541306,458087,543666,459899,545709,462012,548369,463918,551284,466144,553156,468308,555500,470160,558170,472146,560773,474440,562769,476134,565935,478630,567909,480669,570460,482531,573212,484805,575411,486863,577433,488850,580783,491130,582875,493192,585505,495130,587863,497076,590215,499901,592743,501633,595444,503775,597808,505964,600586,507982,603156,510174,605404,512441,607556,514258,611126,516746,613209,518936,615596,520938,618464,523044,620930,525463,623402,527309,626417,529684,628435,532137,631209,534065,633657,536119,636571,538725,638755,540442,641750,542872,643954,545204,646666,547226,649976,549602,652475,551923,654857,553977,657795,556139,659789,558398,662869,560890,665545,562968,667841,565469,670161,567298,673893,569891,676225,572151,678903,574161,681593,576682,684221,579111,686485,580891,689994,583403,692272,585813,695072,588122,698104,590426,700462,592916,703122,594876,706261,597214,708497,599932,711543,602098,714179,604174,717282,606846,719538,608822,722848,611604,725132,613783,727802,615814,731278,618334,733645,620937,736207,623063,739841,625765,742100,628002,745062,630186,747920,632409,750835,635315,753451,637363,756545,639681,759015,642507,762043,644688,764763,647120,767326,649496,770084,651685,774238,654605,776434,656933,779091,659408,782031,661580,784846,664430,787678,666504,791335,669144,793521,671731,796467,673855,799421,676315,802637,679070,805163,681066,808670,684040,811334,686666,814110,688742,817384,691318,820086,694081,822616,696255,826180,698812,828578,701222,832324,703908,835498,706314,838027,709312,840723,711517,844268,714071,846876,716763,849694,718996,853200,721797,856104,724420,858568,726492,