QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589205#7416. GrammarlyBreakPlusAC ✓10ms11288kbC++141.6kb2024-09-25 16:39:502024-09-25 16:39:51

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 16:39:51]
  • 评测
  • 测评结果:AC
  • 用时:10ms
  • 内存:11288kb
  • [2024-09-25 16:39:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
namespace math{
	const ll N = 300005;
	ll fac[N+5],pw[N+5],inv[N+5];
	ll qpow(ll a,ll b){
		ll ans=1,base=a;
		while(b){
			if(b&1) ans=ans*base%mod;
			base=base*base%mod; b>>=1;
		}
		return ans;
	}
	void init(){
		fac[0]=inv[0]=pw[0]=1;
		for(ll i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod,pw[i]=pw[i-1]*2%mod;
		inv[N]=qpow(fac[N],mod-2);
		for(ll i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
	}
	inline ll binom(ll x,ll y){
		if(x<0 || y<0 || x<y) return 0;
		return fac[x]*inv[y]%mod*inv[x-y]%mod;
	}
	inline ll perm(ll x,ll y){
		if(x<0 || y<0 || x<y) return 0;
		return fac[x]*inv[x-y]%mod;
	}
}
ll ans;
using namespace math;
char s[300005];
ll fun(ll x,ll y,ll w){
	x=max(x, w); if(x>y) return 0;
	return (binom(y+1,w+1)-binom(x,w+1)+mod)%mod;
}
ll n;
void recalc(ll l,ll r){
//	cout<<"recalcing "<<l<<","<<r<<endl;
//	cout<<"ans = "<<ans<<endl;
	for(ll p=l-1;p<r;p++){
		ans=(ans-fun(n-r+p,n-1,p)+mod)%mod;
	}
//	cout<<"origin: "<<ans<<endl;
	ans=(ans+(r-l+1)*binom(l-1+n-r,n-r))%mod;
//	cout<<"all: "<<ans<<endl;
	if(l>1){
		for(ll i=l;i<r;i++){
			ans=(ans+(i-l+1)*binom(l-2+n-i,n-i))%mod;
		}
	}
	if(r<n){
		for(ll i=l+1;i<=r;i++){
			ans=(ans+(r-i+1)*binom(i-2+n-r,i-1))%mod;
		}
	}
//	cout<<"now: "<<ans<<endl;
}
int main(){
	init();
	scanf("%s", s+1);
	n=strlen(s+1);
	ans=pw[n]-1;
	
//	cout<<"first "<<ans<<endl;
	for(ll i=1;i<=n;){
		ll j=i;
		while(j<n && s[j+1]==s[i]) j++;
		recalc(i,j);
		i=j+1;
	}
	printf("%lld\n", ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 10932kb

input:

abba

output:

13

result:

ok 1 number(s): "13"

Test #2:

score: 0
Accepted
time: 4ms
memory: 10932kb

input:

benbeipo

output:

255

result:

ok 1 number(s): "255"

Test #3:

score: 0
Accepted
time: 4ms
memory: 10992kb

input:

iqiiiiiiqq

output:

300

result:

ok 1 number(s): "300"

Test #4:

score: 0
Accepted
time: 4ms
memory: 10996kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

output:

35

result:

ok 1 number(s): "35"

Test #5:

score: 0
Accepted
time: 0ms
memory: 10848kb

input:

u

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3ms
memory: 10932kb

input:

yy

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 10944kb

input:

bg

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 3ms
memory: 10952kb

input:

qqq

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 3ms
memory: 11032kb

input:

yyh

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 0ms
memory: 10928kb

input:

cccc

output:

4

result:

ok 1 number(s): "4"

Test #11:

score: 0
Accepted
time: 4ms
memory: 10936kb

input:

kknn

output:

13

result:

ok 1 number(s): "13"

Test #12:

score: 0
Accepted
time: 4ms
memory: 11188kb

input:

ttttt

output:

5

result:

ok 1 number(s): "5"

Test #13:

score: 0
Accepted
time: 4ms
memory: 10928kb

input:

aaaba

output:

25

result:

ok 1 number(s): "25"

Test #14:

score: 0
Accepted
time: 0ms
memory: 10884kb

input:

kktkktktkktttktkttktttkttkttkt

output:

974185013

result:

ok 1 number(s): "974185013"

Test #15:

score: 0
Accepted
time: 4ms
memory: 10928kb

input:

dddydydyddyyyddddydydddydyyyyyydyyyyyyddyydyyddddyyddyydyyyddydyyyyydyddyyydyydydyddydyyddddyyyyydyyyyyyydyddddyydddydydyydddyyyyyyydyydddyydyddydyydddddyyyyyddddyyddyydyddydddyyddyydyyddyyydddyddyyydddyyddydddyyyyydyddydydyydydddyydddyddyydydyddddydyyydyddydddyyddddyydyyydddyddyyydyddydddyyyyyyydyy

output:

267479314

result:

ok 1 number(s): "267479314"

Test #16:

score: 0
Accepted
time: 4ms
memory: 10936kb

input:

ihiiiihihihhhhhihhiiihhihhihihhihihihhiihhhiihiiiiiiihhihiihhhihihihhiiiihhiiiihiihiihihhihhhiihhiiihhhhiiiiihihihhiihiihhhihhiiihhihhiihhiihiiihhiiiihihhihihiihhhiihiihihiihhhhihhhhhhiihhiihihhihhhhhihhiihhiihiiihihhiiiiiihhhiiiiiihhihihiihiiihihhihiiiihhhhhihihhihiihhihhihhiiihiiiiihiiiihhihiiihih...

output:

490411472

result:

ok 1 number(s): "490411472"

Test #17:

score: 0
Accepted
time: 5ms
memory: 10968kb

input:

veeeevvevvvvvvvvvevveveeeveeeeveeeeveevveveevvvvveeeeevvvveeeevvevvvevevveeeevvevvvvvveeeveevvevveeeeeeevevevvevvevevveevvvvveveeeveevevvvvevevveeevvvvvveveevvvveeevvvveevvvveevvvveevvevevveeeeeeveeveveeveeveevevevvvevvevvvvvvevvveevveevvveeevevveeeveeeeeveveeevevveevevevvveeeveevevvevvvveevveeevvev...

output:

395835613

result:

ok 1 number(s): "395835613"

Test #18:

score: 0
Accepted
time: 10ms
memory: 11104kb

input:

eeeeeeeekkkkekkeekkkkeeeeeeeeekeeekkkekkkkekekeeekeekeekekekeekekkkekekeeeekkkkkeekkekeekekkeeeekekeekeekkkeekkkkkekekeekkkeekekekekeeeeeeekkekekeekkeeekekkeekeeekeekkekekekkkkeeekekkeeeeekkkeeeeeeekeeekkkkkkkeeeeeekeeeeeeekeekekkkkeekkkeeeeeeekekekekkkeekeeekkkkkeekkkeeeeekkkeekkeekeeekkeeeekekeekk...

output:

854650474

result:

ok 1 number(s): "854650474"

Test #19:

score: 0
Accepted
time: 2ms
memory: 10808kb

input:

bbibibuibiubbiuubbbibbuibuiuib

output:

931071212

result:

ok 1 number(s): "931071212"

Test #20:

score: 0
Accepted
time: 0ms
memory: 10928kb

input:

ggxgyxxgyyyyyggxxggxyxygxyxggyygggggggxggxyxggxgxxgxyygygxxyxxgxggxxgxggyxxxgggygxyxgggyyyxxxxxgyxggxygygyygyxgyggggxxygggxgyyyyyxxyyxgxyxxyygxxxxxgyyygygxygxyxxyxggyxyxygygxygxgxgxggyggyggxyxyyxygxyxxygxyxyygxyygxxyxxygyyggyyggygxxxgggxgxyyggxygyxgxxxxgxggygyygxggygygxyyyxyxxxggxgxxygxgxxygyggygggx

output:

649661487

result:

ok 1 number(s): "649661487"

Test #21:

score: 0
Accepted
time: 0ms
memory: 10808kb

input:

otohhhotohhhotohthotooththtothohthtttthhhoohotooohhohhohhooohhtotthtoototohhoohoohhotottoooohhothtohohththtthttotoohtothttothohoohtoooththoooohhhoooohtohotthttthothoohohhotothothhtthohhooooohotooothhhttthooothttthhotohttohttthtthttotthhthhtohtotthhohhthohooohotottothohttohhtohttoootohhhtoohttoootthh...

output:

965561176

result:

ok 1 number(s): "965561176"

Test #22:

score: 0
Accepted
time: 4ms
memory: 11024kb

input:

nneeenennezzezeeeznnzznenneenzzeezznzzeezneezzznnenzneennnnznnnneeznenezzznnezezeeznnezenznzneznzzzenenzznnzeezenenzneeznnenenezzenezzenznzzeeeezezenzenzennzneezzezzennezzznnzenneeznnneezeeenezeezeeezneeeznneeeenneznznezeennzzeenzezznennznznnennnzzznnznneneeennneeeeznezzznnneznzenennzzeznzezzezzennn...

output:

963316318

result:

ok 1 number(s): "963316318"

Test #23:

score: 0
Accepted
time: 6ms
memory: 11152kb

input:

fuuulfuulllffllfuulfflffufluufffuflufuffllluullffffluuflulfulullfffluuullulfuufullluuflfllffllluululffflluuulluflulufufufflllulllffflfuufulfllfflulfluufllfllluulfullfuflllfuufuulfufffulfuulfuuuuulllfffllflufulflufuflluulfulfuulfuluuululuufllluuuulullufffluluflfffuuuluuuuuluffuuffffffuuuuuuulflufufll...

output:

469546709

result:

ok 1 number(s): "469546709"

Test #24:

score: 0
Accepted
time: 0ms
memory: 11232kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

300000

result:

ok 1 number(s): "300000"

Test #25:

score: 0
Accepted
time: 9ms
memory: 11232kb

input:

kekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekeke...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #26:

score: 0
Accepted
time: 4ms
memory: 11100kb

input:

keekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekke...

output:

232335975

result:

ok 1 number(s): "232335975"

Test #27:

score: 0
Accepted
time: 9ms
memory: 11220kb

input:

zkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyq...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #28:

score: 0
Accepted
time: 9ms
memory: 11232kb

input:

zkkakaankaanannrkaanannrannrnrrskaanannrannrnrrsannrnrrsnrrsrssckaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwkaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwannrnrrsnrrsrsscnrrsrsscrsscsccwnrrsrsscrsscsccwrsscsccwsccwcwwykaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrs...

output:

292840925

result:

ok 1 number(s): "292840925"

Test #29:

score: 0
Accepted
time: 3ms
memory: 11288kb

input:

yiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufd...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #30:

score: 0
Accepted
time: 9ms
memory: 11096kb

input:

yiiaiaajiaajajjziaajajjzajjzjzzoiaajajjzajjzjzzoajjzjzzojzzozoosiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxajjzjzzojzzozoosjzzozooszoosossxjzzozooszoosossxzoosossxossxsxxviaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzo...

output:

538020582

result:

ok 1 number(s): "538020582"

Test #31:

score: 0
Accepted
time: 9ms
memory: 11152kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

436599269

result:

ok 1 number(s): "436599269"

Test #32:

score: 0
Accepted
time: 9ms
memory: 11228kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

452097214

result:

ok 1 number(s): "452097214"

Test #33:

score: 0
Accepted
time: 9ms
memory: 11220kb

input:

kkkkkkkkkkkkkkkkkkkkkksssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssscccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

51148515

result:

ok 1 number(s): "51148515"

Test #34:

score: 0
Accepted
time: 6ms
memory: 11220kb

input:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrryyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggccccccccccccccccccccccccccccccccccccccccc...

output:

398270601

result:

ok 1 number(s): "398270601"

Test #35:

score: 0
Accepted
time: 6ms
memory: 11224kb

input:

eehhhhhhhhhhhhhhhhhhhmmmwwwwwrrrrrrrrrrzzzzzzzzzzzzzzzzhhhhppppppppppppppppppppppppkkkkklllllggggggquuuukrrrrrrrzzzzzzzzzzzppppjjjjjjjjjjjjjjjjjjjgggggggggggzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkklldddddduuuuutttttttttttttxxxxxxxxxxxxdddddddddddddddmmmmmmddddddddddddbbbbbbccccccmoooooooooo...

output:

685442319

result:

ok 1 number(s): "685442319"

Test #36:

score: 0
Accepted
time: 8ms
memory: 11100kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

360917686

result:

ok 1 number(s): "360917686"

Test #37:

score: 0
Accepted
time: 8ms
memory: 11152kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

450457957

result:

ok 1 number(s): "450457957"

Test #38:

score: 0
Accepted
time: 8ms
memory: 11276kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

679473094

result:

ok 1 number(s): "679473094"

Test #39:

score: 0
Accepted
time: 4ms
memory: 11236kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

215673856

result:

ok 1 number(s): "215673856"

Test #40:

score: 0
Accepted
time: 3ms
memory: 11240kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

940702393

result:

ok 1 number(s): "940702393"

Test #41:

score: 0
Accepted
time: 6ms
memory: 11236kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

389598315

result:

ok 1 number(s): "389598315"

Test #42:

score: 0
Accepted
time: 6ms
memory: 11284kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

617812509

result:

ok 1 number(s): "617812509"

Test #43:

score: 0
Accepted
time: 9ms
memory: 11280kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

689671191

result:

ok 1 number(s): "689671191"

Test #44:

score: 0
Accepted
time: 3ms
memory: 11216kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

505827379

result:

ok 1 number(s): "505827379"

Test #45:

score: 0
Accepted
time: 3ms
memory: 11104kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

290367667

result:

ok 1 number(s): "290367667"

Test #46:

score: 0
Accepted
time: 3ms
memory: 11236kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

631912358

result:

ok 1 number(s): "631912358"

Test #47:

score: 0
Accepted
time: 8ms
memory: 11224kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

433834157

result:

ok 1 number(s): "433834157"

Test #48:

score: 0
Accepted
time: 9ms
memory: 11180kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

729374198

result:

ok 1 number(s): "729374198"

Test #49:

score: 0
Accepted
time: 9ms
memory: 11232kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

11646013

result:

ok 1 number(s): "11646013"

Test #50:

score: 0
Accepted
time: 6ms
memory: 11228kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

351477104

result:

ok 1 number(s): "351477104"

Test #51:

score: 0
Accepted
time: 6ms
memory: 11216kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

957526281

result:

ok 1 number(s): "957526281"

Test #52:

score: 0
Accepted
time: 6ms
memory: 11236kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

529641898

result:

ok 1 number(s): "529641898"

Test #53:

score: 0
Accepted
time: 3ms
memory: 11224kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

210262893

result:

ok 1 number(s): "210262893"

Test #54:

score: 0
Accepted
time: 6ms
memory: 11280kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

911032433

result:

ok 1 number(s): "911032433"

Test #55:

score: 0
Accepted
time: 9ms
memory: 11232kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

937163682

result:

ok 1 number(s): "937163682"

Test #56:

score: 0
Accepted
time: 6ms
memory: 11224kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

334206357

result:

ok 1 number(s): "334206357"

Test #57:

score: 0
Accepted
time: 10ms
memory: 11280kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

827627696

result:

ok 1 number(s): "827627696"

Test #58:

score: 0
Accepted
time: 4ms
memory: 11208kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

686365858

result:

ok 1 number(s): "686365858"

Test #59:

score: 0
Accepted
time: 9ms
memory: 11156kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

974448194

result:

ok 1 number(s): "974448194"

Test #60:

score: 0
Accepted
time: 9ms
memory: 11104kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

670612527

result:

ok 1 number(s): "670612527"