Submission details
Task:Fibonacci towers
Sender:aalto26km_013
Submission time:2026-11-16 17:29:12 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.04 sdetails
#40.04 sdetails
#50.04 sdetails
#60.04 sdetails
#70.04 sdetails
#80.04 sdetails
#90.04 sdetails
#100.07 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.04 sdetails
#140.04 sdetails
#150.04 sdetails
#16ACCEPTED0.04 sdetails
#170.04 sdetails
#180.04 sdetails
#190.04 sdetails
#200.07 sdetails
#21ACCEPTED0.04 sdetails
#22ACCEPTED0.04 sdetails
#23ACCEPTED0.04 sdetails
#24ACCEPTED0.04 sdetails
#250.04 sdetails
#26ACCEPTED0.04 sdetails
#270.04 sdetails
#280.04 sdetails
#290.04 sdetails
#300.33 sdetails
#31ACCEPTED0.06 sdetails
#32ACCEPTED0.04 sdetails
#33ACCEPTED0.09 sdetails
#34ACCEPTED0.07 sdetails
#35ACCEPTED0.06 sdetails
#36ACCEPTED0.06 sdetails
#370.07 sdetails
#38ACCEPTED0.07 sdetails
#390.08 sdetails
#40--details
#41--details
#42--details
#43--details
#44--details
#45--details
#46--details
#47--details
#48--details
#49--details
#50--details
#51--details
#52--details
#53--details
#54--details
#55--details
#56--details
#57--details
#58--details
#59--details
#60--details
#61--details
#62--details
#63--details
#64--details
#65--details
#66--details
#67--details
#68--details
#69--details
#70--details
#71--details
#72--details
#73--details
#74--details
#75--details
#76--details
#77--details
#78--details
#79--details
#80--details

Code


M = 998244353

a, b = map(int, input().split())

mat = [[0] * a for i in range(a)]

for i in range(a-1):
    mat[i+1][i] = 1
mat[0][0] = 1
mat[0][a-1] = 1


vec = [1] + [0] * (a-1)



def mult(m1, m2):
    out = [[0] * a for i in range(a)]
    for i in range(a):
        for j in range(a):
            for k in range(a):
                out[i][j] += m1[i][k] * m2[k][j]
    return out


def exp(mat, n):
    if n==1: return mat
    n2 = n//2
    m2 = exp(mat, n2)
    out = mult(m2, m2)
    if n2*2 < n:
        out = mult(out, mat)
    return out

final = exp(mat, b)
print(final[0][0])
# out = 0
# for i in range(b):
#     out += final[0][i] * vec
# print()

Test details

Test 1

Verdict: ACCEPTED

input
2 10

correct output
89

user output
89

Test 2

Verdict: ACCEPTED

input
2 6

correct output
13

user output
13

Test 3

Verdict: ACCEPTED

input
2 8

correct output
34

user output
34

Test 4

Verdict:

input
2 68

correct output
977351119

user output
117669030460994

Test 5

Verdict:

input
2 78

correct output
20929410

user output
14472334024676221

Test 6

Verdict:

input
2 76

correct output
878806424

user output
5527939700884757

Test 7

Verdict:

input
2 485

correct output
908660084

user output
165389585710146294587522349272...

Test 8

Verdict:

input
2 519

correct output
838514871

user output
210905510872795811521673602670...

Test 9

Verdict:

input
2 602

correct output
892152152

user output
467801993911057346969253632393...

Test 10

Verdict:

input
2 165714

correct output
921473843

user output
(empty)

Error:
Traceback (most recent call last):
  File "/box/input/code.py", line 38, in <module>
    print(final[0][0])
ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

Test 11

Verdict: ACCEPTED

input
3 6

correct output
6

user output
6

Test 12

Verdict: ACCEPTED

input
3 8

correct output
13

user output
13

Test 13

Verdict: ACCEPTED

input
2 7

correct output
21

user output
21

Test 14

Verdict:

input
3 78

correct output
198155624

user output
5431645680297

Test 15

Verdict:

input
2 76

correct output
878806424

user output
5527939700884757

Test 16

Verdict: ACCEPTED

input
3 49

correct output
83316385

user output
83316385

Test 17

Verdict:

input
2 519

correct output
838514871

user output
210905510872795811521673602670...

Test 18

Verdict:

input
3 602

correct output
575081686

user output
527914445527581146008784903558...

Test 19

Verdict:

input
2 166

correct output
833010588

user output
356000755459584589632228765813...

Test 20

Verdict:

input
2 187222

correct output
206734446

user output
(empty)

Error:
Traceback (most recent call last):
  File "/box/input/code.py", line 38, in <module>
    print(final[0][0])
ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

Test 21

Verdict: ACCEPTED

input
2 7

correct output
21

user output
21

Test 22

Verdict: ACCEPTED

input
5 8

correct output
5

user output
5

Test 23

Verdict: ACCEPTED

input
2 8

correct output
34

user output
34

Test 24

Verdict: ACCEPTED

input
5 49

correct output
486716

user output
486716

Test 25

Verdict:

input
2 52

correct output
409340464

user output
53316291173

Test 26

Verdict: ACCEPTED

input
5 61

correct output
14215310

user output
14215310

Test 27

Verdict:

input
2 166

correct output
833010588

user output
356000755459584589632228765813...

Test 28

Verdict:

input
2 188

correct output
914862760

user output
140986979094766914331203559197...

Test 29

Verdict:

input
5 611

correct output
386811672

user output
209237351914603947279607274979...

Test 30

Verdict:

input
4 672099

correct output
5039638

user output
(empty)

Error:
Traceback (most recent call last):
  File "/box/input/code.py", line 38, in <module>
    print(final[0][0])
ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

Test 31

Verdict: ACCEPTED

input
77 10

correct output
1

user output
1

Test 32

Verdict: ACCEPTED

input
76 1

correct output
1

user output
1

Test 33

Verdict: ACCEPTED

input
80 7

correct output
1

user output
1

Test 34

Verdict: ACCEPTED

input
72 56

correct output
1

user output
1

Test 35

Verdict: ACCEPTED

input
57 97

correct output
42

user output
42

Test 36

Verdict: ACCEPTED

input
54 58

correct output
6

user output
6

Test 37

Verdict:

input
50 639

correct output
373574336

user output
2650671546158885

Test 38

Verdict: ACCEPTED

input
58 195

correct output
5403

user output
5403

Test 39

Verdict:

input
61 694

correct output
605984493

user output
233619731917083

Test 40

Verdict:

input
9 616206422053543989

correct output
952862778

user output
(empty)

Test 41

Verdict:

input
6 169825965437345849

correct output
513277084

user output
(empty)

Test 42

Verdict:

input
5 191867851255868863

correct output
33742481

user output
(empty)

Test 43

Verdict:

input
9 625431978270398522

correct output
737838270

user output
(empty)

Test 44

Verdict:

input
8 688779226095035965

correct output
162344930

user output
(empty)

Test 45

Verdict:

input
10 802140689263714569

correct output
90271065

user output
(empty)

Test 46

Verdict:

input
6 326105735534681902

correct output
815511427

user output
(empty)

Test 47

Verdict:

input
6 714378023239269070

correct output
974264931

user output
(empty)

Test 48

Verdict:

input
8 389060406667759103

correct output
997632165

user output
(empty)

Test 49

Verdict:

input
5 752611790930241374

correct output
663785595

user output
(empty)

Test 50

Verdict:

input
9 616206422053543989

correct output
952862778

user output
(empty)

Test 51

Verdict:

input
9 616206422053543989

correct output
952862778

user output
(empty)

Test 52

Verdict:

input
10 292432805466778024

correct output
54188787

user output
(empty)

Test 53

Verdict:

input
12 877206118126603157

correct output
50978391

user output
(empty)

Test 54

Verdict:

input
15 106209626593822568

correct output
26611817

user output
(empty)

Test 55

Verdict:

input
20 599479100988098599

correct output
119658586

user output
(empty)

Test 56

Verdict:

input
19 751085324932436268

correct output
362164431

user output
(empty)

Test 57

Verdict:

input
13 653792349017119940

correct output
727329363

user output
(empty)

Test 58

Verdict:

input
14 922927469528725341

correct output
702679243

user output
(empty)

Test 59

Verdict:

input
18 278820978471154000

correct output
447470474

user output
(empty)

Test 60

Verdict:

input
19 595145428494262541

correct output
321383191

user output
(empty)

Test 61

Verdict:

input
16 733419934325111819

correct output
603915854

user output
(empty)

Test 62

Verdict:

input
42 977794035917013551

correct output
535001165

user output
(empty)

Test 63

Verdict:

input
46 107297864267805308

correct output
557129508

user output
(empty)

Test 64

Verdict:

input
47 423649320883482177

correct output
894439428

user output
(empty)

Test 65

Verdict:

input
35 923635615021083310

correct output
306200203

user output
(empty)

Test 66

Verdict:

input
27 119042622192684556

correct output
95698341

user output
(empty)

Test 67

Verdict:

input
50 394425873219136058

correct output
461849248

user output
(empty)

Test 68

Verdict:

input
27 702344952743354850

correct output
361328763

user output
(empty)

Test 69

Verdict:

input
34 148052957467783205

correct output
883611228

user output
(empty)

Test 70

Verdict:

input
49 120057477600708020

correct output
411727310

user output
(empty)

Test 71

Verdict:

input
77 985532091144101696

correct output
533259046

user output
(empty)

Test 72

Verdict:

input
76 62568531781086688

correct output
111230040

user output
(empty)

Test 73

Verdict:

input
80 638842883372078079

correct output
843571033

user output
(empty)

Test 74

Verdict:

input
72 568029317340376926

correct output
760917479

user output
(empty)

Test 75

Verdict:

input
57 993363883840818838

correct output
125996687

user output
(empty)

Test 76

Verdict:

input
54 587462523883449402

correct output
707247678

user output
(empty)

Test 77

Verdict:

input
50 654341799647462242

correct output
823275735

user output
(empty)

Test 78

Verdict:

input
58 198843859011456415

correct output
392227014

user output
(empty)

Test 79

Verdict:

input
61 710225245014179861

correct output
352309063

user output
(empty)

Test 80

Verdict:

input
81 435847411137743327

correct output
639314946

user output
(empty)