QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641179#7416. GrammarlyzhenghanyunAC ✓17ms13428kbC++201.7kb2024-10-14 19:00:482024-10-14 19:00:50

Judging History

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

  • [2024-10-14 19:00:50]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:13428kb
  • [2024-10-14 19:00:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 5;
const ll mod = 998244353;

ll fac[N << 1], ifac[N << 1];

inline void get_fac(ll n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[0] = ifac[1] = 1;
	for (int i = 2; i <= n; ++i) {
		ifac[i] = (mod - mod / i) * ifac[mod % i] % mod;
	}
	for (int i = 1; i <= n; ++i) {
		ifac[i] = ifac[i] * ifac[i - 1] % mod;
	}
}

inline ll C(ll n, ll m) {
	if (n < m) {
		return 0;
	}
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

ll n, ans;

string s;

inline ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

inline ll inv(ll a) {
	return qpow(a, mod - 2);
}

inline ll S(ll n, ll m) {
	if (m > n) {
		return 0;
	}
	return C(n + 1, m + 1);
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	get_fac(6e5);
	cin >> s;
	n = s.size();
	s = "#" + s;
	ans = qpow(2, n) - 1;
	for (int i = 1; i <= n; ++i) {
		int j = i;
		while (j < n && s[j + 1] == s[j]) {
			++j;
		}
		for (int p = i - 1; p <= j - 1; ++p) {
			ans = (ans - S(n - 1, p) + S(n - j + p - 1, p) + mod) % mod;
		}
		for (int p = i; p <= j; ++p) {
			ll t = C(i - 1 + n - p, i - 1);
			if (p != j) {
				t = (t - C(i + n - p - 2, i - 1) + mod) % mod;
			}
			ans = (ans + t * (p - i + 1)) % mod;
		}
		for (int p = i + 1; p <= j; ++p) {
			ll t = C(n + p - j - 1, n - j) - C(n + p - j - 2, n - j);
			ans = (ans + t * (j - p + 1)) % mod;
		}
		i = j;
	}
	cout << ans << "\n";
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 13192kb

input:

abba

output:

13

result:

ok 1 number(s): "13"

Test #2:

score: 0
Accepted
time: 7ms
memory: 12964kb

input:

benbeipo

output:

255

result:

ok 1 number(s): "255"

Test #3:

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

input:

iqiiiiiiqq

output:

300

result:

ok 1 number(s): "300"

Test #4:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

output:

35

result:

ok 1 number(s): "35"

Test #5:

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

input:

u

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

yy

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 7ms
memory: 12852kb

input:

bg

output:

3

result:

ok 1 number(s): "3"

Test #8:

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

input:

qqq

output:

3

result:

ok 1 number(s): "3"

Test #9:

score: 0
Accepted
time: 7ms
memory: 12984kb

input:

yyh

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 11ms
memory: 13196kb

input:

cccc

output:

4

result:

ok 1 number(s): "4"

Test #11:

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

input:

kknn

output:

13

result:

ok 1 number(s): "13"

Test #12:

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

input:

ttttt

output:

5

result:

ok 1 number(s): "5"

Test #13:

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

input:

aaaba

output:

25

result:

ok 1 number(s): "25"

Test #14:

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

input:

kktkktktkktttktkttktttkttkttkt

output:

974185013

result:

ok 1 number(s): "974185013"

Test #15:

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

input:

dddydydyddyyyddddydydddydyyyyyydyyyyyyddyydyyddddyyddyydyyyddydyyyyydyddyyydyydydyddydyyddddyyyyydyyyyyyydyddddyydddydydyydddyyyyyyydyydddyydyddydyydddddyyyyyddddyyddyydyddydddyyddyydyyddyyydddyddyyydddyyddydddyyyyydyddydydyydydddyydddyddyydydyddddydyyydyddydddyyddddyydyyydddyddyyydyddydddyyyyyyydyy

output:

267479314

result:

ok 1 number(s): "267479314"

Test #16:

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

input:

ihiiiihihihhhhhihhiiihhihhihihhihihihhiihhhiihiiiiiiihhihiihhhihihihhiiiihhiiiihiihiihihhihhhiihhiiihhhhiiiiihihihhiihiihhhihhiiihhihhiihhiihiiihhiiiihihhihihiihhhiihiihihiihhhhihhhhhhiihhiihihhihhhhhihhiihhiihiiihihhiiiiiihhhiiiiiihhihihiihiiihihhihiiiihhhhhihihhihiihhihhihhiiihiiiiihiiiihhihiiihih...

output:

490411472

result:

ok 1 number(s): "490411472"

Test #17:

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

input:

veeeevvevvvvvvvvvevveveeeveeeeveeeeveevveveevvvvveeeeevvvveeeevvevvvevevveeeevvevvvvvveeeveevvevveeeeeeevevevvevvevevveevvvvveveeeveevevvvvevevveeevvvvvveveevvvveeevvvveevvvveevvvveevvevevveeeeeeveeveveeveeveevevevvvevvevvvvvvevvveevveevvveeevevveeeveeeeeveveeevevveevevevvveeeveevevvevvvveevveeevvev...

output:

395835613

result:

ok 1 number(s): "395835613"

Test #18:

score: 0
Accepted
time: 16ms
memory: 13236kb

input:

eeeeeeeekkkkekkeekkkkeeeeeeeeekeeekkkekkkkekekeeekeekeekekekeekekkkekekeeeekkkkkeekkekeekekkeeeekekeekeekkkeekkkkkekekeekkkeekekekekeeeeeeekkekekeekkeeekekkeekeeekeekkekekekkkkeeekekkeeeeekkkeeeeeeekeeekkkkkkkeeeeeekeeeeeeekeekekkkkeekkkeeeeeeekekekekkkeekeeekkkkkeekkkeeeeekkkeekkeekeeekkeeeekekeekk...

output:

854650474

result:

ok 1 number(s): "854650474"

Test #19:

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

input:

bbibibuibiubbiuubbbibbuibuiuib

output:

931071212

result:

ok 1 number(s): "931071212"

Test #20:

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

input:

ggxgyxxgyyyyyggxxggxyxygxyxggyygggggggxggxyxggxgxxgxyygygxxyxxgxggxxgxggyxxxgggygxyxgggyyyxxxxxgyxggxygygyygyxgyggggxxygggxgyyyyyxxyyxgxyxxyygxxxxxgyyygygxygxyxxyxggyxyxygygxygxgxgxggyggyggxyxyyxygxyxxygxyxyygxyygxxyxxygyyggyyggygxxxgggxgxyyggxygyxgxxxxgxggygyygxggygygxyyyxyxxxggxgxxygxgxxygyggygggx

output:

649661487

result:

ok 1 number(s): "649661487"

Test #21:

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

input:

otohhhotohhhotohthotooththtothohthtttthhhoohotooohhohhohhooohhtotthtoototohhoohoohhotottoooohhothtohohththtthttotoohtothttothohoohtoooththoooohhhoooohtohotthttthothoohohhotothothhtthohhooooohotooothhhttthooothttthhotohttohttthtthttotthhthhtohtotthhohhthohooohotottothohttohhtohttoootohhhtoohttoootthh...

output:

965561176

result:

ok 1 number(s): "965561176"

Test #22:

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

input:

nneeenennezzezeeeznnzznenneenzzeezznzzeezneezzznnenzneennnnznnnneeznenezzznnezezeeznnezenznzneznzzzenenzznnzeezenenzneeznnenenezzenezzenznzzeeeezezenzenzennzneezzezzennezzznnzenneeznnneezeeenezeezeeezneeeznneeeenneznznezeennzzeenzezznennznznnennnzzznnznneneeennneeeeznezzznnneznzenennzzeznzezzezzennn...

output:

963316318

result:

ok 1 number(s): "963316318"

Test #23:

score: 0
Accepted
time: 16ms
memory: 13224kb

input:

fuuulfuulllffllfuulfflffufluufffuflufuffllluullffffluuflulfulullfffluuullulfuufullluuflfllffllluululffflluuulluflulufufufflllulllffflfuufulfllfflulfluufllfllluulfullfuflllfuufuulfufffulfuulfuuuuulllfffllflufulflufuflluulfulfuulfuluuululuufllluuuulullufffluluflfffuuuluuuuuluffuuffffffuuuuuuulflufufll...

output:

469546709

result:

ok 1 number(s): "469546709"

Test #24:

score: 0
Accepted
time: 12ms
memory: 13248kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

300000

result:

ok 1 number(s): "300000"

Test #25:

score: 0
Accepted
time: 11ms
memory: 13304kb

input:

kekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekekeke...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #26:

score: 0
Accepted
time: 16ms
memory: 13264kb

input:

keekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekkeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkeekkekeekkeekekkekeekekkeekkekeekekkekeekkeekekkekeekekkeekkekeekkeekekkeekke...

output:

232335975

result:

ok 1 number(s): "232335975"

Test #27:

score: 0
Accepted
time: 15ms
memory: 13156kb

input:

zkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyqzkanrscwyq...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #28:

score: 0
Accepted
time: 12ms
memory: 13268kb

input:

zkkakaankaanannrkaanannrannrnrrskaanannrannrnrrsannrnrrsnrrsrssckaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwkaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrsrsscnrrsrsscrsscsccwannrnrrsnrrsrsscnrrsrsscrsscsccwnrrsrsscrsscsccwrsscsccwsccwcwwykaanannrannrnrrsannrnrrsnrrsrsscannrnrrsnrrs...

output:

292840925

result:

ok 1 number(s): "292840925"

Test #29:

score: 0
Accepted
time: 11ms
memory: 13312kb

input:

yiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufdtqcemhpgwnlryiajzosxvkbufd...

output:

526952119

result:

ok 1 number(s): "526952119"

Test #30:

score: 0
Accepted
time: 7ms
memory: 13228kb

input:

yiiaiaajiaajajjziaajajjzajjzjzzoiaajajjzajjzjzzoajjzjzzojzzozoosiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxiaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzozoosjzzozooszoosossxajjzjzzojzzozoosjzzozooszoosossxjzzozooszoosossxzoosossxossxsxxviaajajjzajjzjzzoajjzjzzojzzozoosajjzjzzojzzo...

output:

538020582

result:

ok 1 number(s): "538020582"

Test #31:

score: 0
Accepted
time: 13ms
memory: 13248kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

436599269

result:

ok 1 number(s): "436599269"

Test #32:

score: 0
Accepted
time: 17ms
memory: 13312kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

452097214

result:

ok 1 number(s): "452097214"

Test #33:

score: 0
Accepted
time: 17ms
memory: 13248kb

input:

kkkkkkkkkkkkkkkkkkkkkksssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssscccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

51148515

result:

ok 1 number(s): "51148515"

Test #34:

score: 0
Accepted
time: 13ms
memory: 13288kb

input:

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrryyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggccccccccccccccccccccccccccccccccccccccccc...

output:

398270601

result:

ok 1 number(s): "398270601"

Test #35:

score: 0
Accepted
time: 13ms
memory: 13264kb

input:

eehhhhhhhhhhhhhhhhhhhmmmwwwwwrrrrrrrrrrzzzzzzzzzzzzzzzzhhhhppppppppppppppppppppppppkkkkklllllggggggquuuukrrrrrrrzzzzzzzzzzzppppjjjjjjjjjjjjjjjjjjjgggggggggggzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkklldddddduuuuutttttttttttttxxxxxxxxxxxxdddddddddddddddmmmmmmddddddddddddbbbbbbccccccmoooooooooo...

output:

685442319

result:

ok 1 number(s): "685442319"

Test #36:

score: 0
Accepted
time: 16ms
memory: 13376kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

360917686

result:

ok 1 number(s): "360917686"

Test #37:

score: 0
Accepted
time: 13ms
memory: 13304kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

450457957

result:

ok 1 number(s): "450457957"

Test #38:

score: 0
Accepted
time: 16ms
memory: 13232kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

679473094

result:

ok 1 number(s): "679473094"

Test #39:

score: 0
Accepted
time: 13ms
memory: 13300kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

215673856

result:

ok 1 number(s): "215673856"

Test #40:

score: 0
Accepted
time: 17ms
memory: 13152kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

940702393

result:

ok 1 number(s): "940702393"

Test #41:

score: 0
Accepted
time: 16ms
memory: 13248kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

389598315

result:

ok 1 number(s): "389598315"

Test #42:

score: 0
Accepted
time: 12ms
memory: 13228kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

617812509

result:

ok 1 number(s): "617812509"

Test #43:

score: 0
Accepted
time: 13ms
memory: 13232kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

689671191

result:

ok 1 number(s): "689671191"

Test #44:

score: 0
Accepted
time: 16ms
memory: 13308kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

505827379

result:

ok 1 number(s): "505827379"

Test #45:

score: 0
Accepted
time: 17ms
memory: 13268kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

290367667

result:

ok 1 number(s): "290367667"

Test #46:

score: 0
Accepted
time: 12ms
memory: 13264kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

631912358

result:

ok 1 number(s): "631912358"

Test #47:

score: 0
Accepted
time: 14ms
memory: 13304kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

433834157

result:

ok 1 number(s): "433834157"

Test #48:

score: 0
Accepted
time: 12ms
memory: 13316kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

729374198

result:

ok 1 number(s): "729374198"

Test #49:

score: 0
Accepted
time: 16ms
memory: 13304kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

11646013

result:

ok 1 number(s): "11646013"

Test #50:

score: 0
Accepted
time: 17ms
memory: 13228kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

351477104

result:

ok 1 number(s): "351477104"

Test #51:

score: 0
Accepted
time: 12ms
memory: 13200kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

957526281

result:

ok 1 number(s): "957526281"

Test #52:

score: 0
Accepted
time: 16ms
memory: 13304kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

529641898

result:

ok 1 number(s): "529641898"

Test #53:

score: 0
Accepted
time: 13ms
memory: 13316kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

210262893

result:

ok 1 number(s): "210262893"

Test #54:

score: 0
Accepted
time: 16ms
memory: 13380kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

911032433

result:

ok 1 number(s): "911032433"

Test #55:

score: 0
Accepted
time: 12ms
memory: 13148kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

937163682

result:

ok 1 number(s): "937163682"

Test #56:

score: 0
Accepted
time: 12ms
memory: 13428kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

334206357

result:

ok 1 number(s): "334206357"

Test #57:

score: 0
Accepted
time: 16ms
memory: 13248kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

827627696

result:

ok 1 number(s): "827627696"

Test #58:

score: 0
Accepted
time: 12ms
memory: 13236kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

686365858

result:

ok 1 number(s): "686365858"

Test #59:

score: 0
Accepted
time: 13ms
memory: 13252kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

974448194

result:

ok 1 number(s): "974448194"

Test #60:

score: 0
Accepted
time: 12ms
memory: 13152kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

670612527

result:

ok 1 number(s): "670612527"