500 998
1 2 530873053
1 3 156306296
1 4 478040476
3 5 303609600
4 6 408024907
5 7 944174442
4 8 79461359
7 9 474561637
2 10 148539742
8 11 517398078
8 12 387309972
6 13 947814955
10 14 96164825
2 15 542189497
10 16 92307048
13 17 664849182
1 18 371378864
14 19 772160941
14 20 635168181
20 21 785677388
7 22 384045503
9 23 998514048
18 24 270719667
4 25 767566166
21 26 175059067
7 27 497680537
21 28 153271159
27 29 297036052
4 30 474118031
16 31 768497643
15 32 957394987
8 33 847608755
9 34 119993073
25 35 2556112
29 36 772839640
30 37 538356431
14 38 987898153
29 39 326573127
26 40 700820441
15 41 837468981
40 42 480685553
12 43 519560677
33 44 483160717
31 45 712226495
11 46 463516975
32 47 914665775
30 48 512876010
44 49 926071683
2 50 637486460
3 51 685100520
4 52 471629515
9 53 428847096
23 54 774485897
49 55 205224244
2 56 952130744
4 57 5037182
26 58 342697057
52 59 120869311
21 60 529856804
13 61 905352610
58 62 98557075
28 63 817492543
13 64 64356557
39 65 964629350
19 66 221337856
30 67 177328177
36 68 967037969
14 69 453381869
19 70 769422203
3 71 112947195
1 72 790605726
33 73 600020760
58 74 631409047
67 75 879330141
42 76 542737120
64 77 723476606
34 78 388339147
64 79 839907065
46 80 492966162
44 81 450368225
8 82 358978952
69 83 107173973
81 84 797025262
23 85 47266638
48 86 22584890
82 87 253696397
67 88 369373045
62 89 110081166
83 90 368497658
37 91 64658363
31 92 366940835
15 93 378990345
7 94 415537987
18 95 45761549
60 96 975252862
20 97 750709912
97 98 882297895
31 99 558319222
13 100 589225605
99 101 710542163
75 102 227265563
33 103 745937703
94 104 224117684
77 105 101126603
4 106 417467556
105 107 603093703
7 108 952758354
91 109 745836455
40 110 396849976
93 111 948849566
49 112 324792328
19 113 978968558
46 114 732536178
113 115 426670789
6 116 129246631
5 117 802362788
41 118 150205311
13 119 396735174
102 120 628020915
11 121 26825400
1 122 703839558
98 123 527091026
95 124 121853839
28 125 900397571
103 126 148109102
56 127 675144780
89 128 259626751
71 129 293654018
125 130 201688308
94 131 798632856
93 132 758582802
120 133 469873101
39 134 926249545
89 135 25051772
93 136 393536020
56 137 185327476
10 138 530846802
117 139 136058547
138 140 798548369
6 141 464111546
38 142 390452094
136 143 85650534
37 144 666470109
136 145 777604766
17 146 375407112
140 147 106159239
105 148 884952840
79 149 675202974
94 150 472444598
38 151 37837566
22 152 924457062
120 153 888904117
8 154 474183376
55 155 125460675
95 156 217023008
108 157 712484598
70 158 457064034
31 159 265056666
98 160 897024531
43 161 156599071
79 162 938651224
4 163 793595438
162 164 78898906
123 165 302843714
112 166 598007225
137 167 697416234
119 168 332959090
30 169 196497395
120 170 893574339
8 171 96549719
40 172 729216452
110 173 929813076
84 174 921768723
167 175 462081970
18 176 861127848
124 177 224351473
174 178 720915547
43 179 835013239
146 180 146157134
96 181 289989847
57 182 207698523
104 183 356432989
147 184 48770959
181 185 853462558
7 186 686249903
24 187 79834701
8 188 790863402
102 189 720449492
42 190 407380905
39 191 959521126
150 192 195596316
177 193 268474171
80 194 843569000
56 195 974041939
187 196 820426586
106 197 744199004
136 198 270601994
63 199 786760683
184 200 12996627
115 201 924863227
12 202 573395513
43 203 532231273
101 204 80829184
58 205 160342041
51 206 390261144
47 207 79184347
109 208 672364203
62 209 55514990
99 210 331310793
39 211 436652015
174 212 181275997
96 213 862891744
43 214 28591681
173 215 257144403
183 216 327115219
98 217 652913371
203 218 99600742
148 219 765449727
87 220 166040926
87 221 950659098
7 222 227476905
168 223 709872299
37 224 658748208
162 225 369492850
108 226 960326000
107 227 964878887
146 228 355869598
165 229 945451088
172 230 219647635
82 231 935082913
145 232 917808490
130 233 954345043
166 234 588875326
125 235 766871843
209 236 341889444
31 237 684876658
121 238 837311781
194 239 166042540
185 240 80387661
41 241 475186165
226 242 984656044
234 243 815950647
59 244 970350042
113 245 630284237
130 246 537942681
43 247 222184485
164 248 857709756
159 249 239240728
36 250 755967213
202 251 532604690
98 252 464501398
178 253 624164524
222 254 913242890
216 255 454256605
153 256 756722842
135 257 273985427
49 258 628382350
200 259 942638677
64 260 321654313
104 261 127592398
253 262 322828619
93 263 673204093
40 264 665007708
262 265 366488131
97 266 616642900
174 267 597646947
69 268 738984535
215 269 841040894
68 270 826767333
71 271 569016574
253 272 806525940
42 273 585606200
105 274 335258540
252 275 48040609
70 276 688173231
195 277 550139672
76 278 459052877
56 279 991614487
163 280 378388789
68 281 28187231
231 282 182660381
188 283 343208148
277 284 77889115
70 285 275440370
104 286 959436622
240 287 535466600
210 288 606348981
283 289 576109474
172 290 921646769
16 291 851718658
134 292 426621198
40 293 430683149
71 294 176024895
140 295 146492897
29 296 40749534
115 297 602403539
286 298 970756924
83 299 792954626
237 300 481771642
76 301 566119889
115 302 528224831
44 303 839532911
143 304 400967153
129 305 640137527
48 306 503568902
244 307 767397535
46 308 840596915
142 309 299070645
138 310 241335972
80 311 419823268
295 312 92121178
134 313 8983465
7 314 164501946
226 315 325153851
194 316 892105588
243 317 300751600
202 318 951523242
172 319 49194679
292 320 762222534
74 321 761640806
164 322 497303722
320 323 104630097
209 324 923212946
148 325 449402878
197 326 986814186
43 327 170610520
171 328 931366040
102 329 235235459
248 330 121508175
35 331 530975904
265 332 131782927
126 333 596075436
78 334 818324183
278 335 753065868
297 336 715519201
148 337 465945272
290 338 780025991
52 339 11161061
131 340 840021049
288 341 935331731
56 342 193865100
288 343 821257164
11 344 739644591
335 345 376525361
24 346 504945800
152 347 330299385
209 348 652514527
27 349 348436986
39 350 178478857
165 351 719981635
75 352 79589978
160 353 510462934
203 354 467228387
265 355 8129461
178 356 922105110
63 357 536278115
344 358 218875299
12 359 436893992
275 360 406167727
319 361 149802059
232 362 353293303
283 363 463055588
96 364 466473861
342 365 904411153
333 366 378229442
288 367 853639545
260 368 663553037
138 369 847571147
50 370 442518448
116 371 173321512
269 372 775967465
299 373 498634093
369 374 689186352
302 375 795967280
119 376 816733747
299 377 907999753
266 378 583762034
334 379 909114229
74 380 465791075
3 381 880662905
13 382 658782309
29 383 593209096
266 384 593787410
370 385 427038229
32 386 829390718
382 387 814677561
35 388 250292869
380 389 762964406
277 390 493756273
251 391 890231208
215 392 208368947
127 393 936898309
119 394 362936031
87 395 588730306
272 396 754632480
344 397 482375853
204 398 305517829
95 399 596763261
199 400 549435864
366 401 954472286
205 402 462719083
187 403 983450533
391 404 834412507
356 405 828061234
337 406 763453833
45 407 221454030
366 408 605498913
109 409 285181359
237 410 401366026
406 411 109710490
189 412 183696072
60 413 967656241
323 414 290896555
286 415 944786833
215 416 918265791
413 417 899936521
154 418 156104937
289 419 990156352
396 420 750704293
325 421 250089079
157 422 699785513
36 423 595027121
63 424 309611309
73 425 21992280
207 426 822899881
121 427 214611120
21 428 177987469
80 429 240272562
273 430 967666619
25 431 870478188
207 432 115998100
363 433 844059164
31 434 156856355
372 435 914369252
132 436 141012493
11 437 177151839
241 438 89186281
19 439 70899680
227 440 482166044
244 441 764230576
85 442 559793383
180 443 303602519
44 444 646820800
48 445 594406853
307 446 163889947
364 447 415700532
71 448 358612075
68 449 954608496
246 450 495264754
347 451 583488746
382 452 539222132
1 453 394763301
279 454 195207657
244 455 484428247
5 456 333452136
434 457 662235363
206 458 282022582
422 459 131173999
444 460 565632444
385 461 154589588
312 462 428382036
326 463 623402877
77 464 447401850
457 465 87078478
263 466 441772023
232 467 636736437
413 468 293364582
182 469 684538158
354 470 845117431
201 471 286127265
119 472 307092693
311 473 613891571
330 474 1598713
14 475 331543767
366 476 369065231
237 477 833187235
215 478 2906368
446 479 780169150
58 480 353687150
206 481 273304314
182 482 199369771
187 483 438573172
275 484 438250674
359 485 483224023
231 486 326074620
179 487 54849207
153 488 129163445
259 489 405671435
355 490 967855255
419 491 593566546
269 492 774320799
72 493 571748957
283 494 338140754
450 495 971428632
482 496 879810976
340 497 716924850
399 498 791683185
39 499 776123616
248 500 727282676
1 2 365529510
1 3 768415519
2 4 545980645
4 5 399690888
5 6 859270332
6 7 480140342
2 8 92453585
8 9 660178728
1 10 487114895
7 11 939283974
8 12 394616411
9 13 348128533
4 14 144984201
6 15 223704553
7 16 448707614
3 17 967248471
13 18 946224206
15 19 191843641
10 20 96717598
4 21 379338977
20 22 621321186
16 23 598201694
23 24 471507893
11 25 659381604
3 26 358743998
20 27 484517695
22 28 242855963
12 29 454181762
9 30 102711082
18 31 254676720
13 32 629922279
28 33 332498268
2 34 193604369
18 35 650584352
13 36 313253336
11 37 248562254
21 38 294254976
29 39 671804829
9 40 251276416
35 41 790513425
30 42 875515561
29 43 186177081
21 44 919298118
9 45 216681076
13 46 925925617
6 47 535101071
26 48 226339727
11 49 692065314
29 50 17972346
21 51 998895559
2 52 684731315
33 53 657687932
40 54 941165293
34 55 159484868
44 56 696574773
26 57 641387428
30 58 852319660
12 59 152862767
8 60 301968476
50 61 563878162
51 62 847741199
12 63 619165531
52 64 987958410
62 65 24007265
48 66 409693462
18 67 153428263
48 68 438429816
57 69 526969988
33 70 823959994
42 71 740924145
37 72 723028804
25 73 651790868
73 74 620049872
2 75 343140610
14 76 765225437
19 77 271290156
43 78 929688334
15 79 855448841
77 80 18817679
1 81 518848251
68 82 463477904
2 83 526111919
30 84 189333022
31 85 333149493
46 86 521867413
7 87 570928063
44 88 271033057
31 89 742621942
19 90 236275929
82 91 223376025
33 92 352841606
21 93 842392508
77 94 362859913
4 95 171414748
70 96 737101256
92 97 78948278
59 98 877771187
82 99 597397981
92 100 610120956
95 101 970936452
46 102 430016573
26 103 260007029
78 104 304766891
10 105 670625664
25 106 475333939
20 107 940345315
24 108 627486152
38 109 125992122
48 110 24007667
24 111 267470025
68 112 651368965
85 113 53514460
68 114 411870491
80 115 580672149
109 116 305733858
98 117 401736496
113 118 146386257
109 119 457109001
25 120 165800934
72 121 481222529
93 122 223010643
101 123 302218367
68 124 278279528
25 125 882098475
56 126 701253939
80 127 498188833
3 128 451910951
98 129 960800697
63 130 769675398
78 131 346057178
57 132 63809538
121 133 970080306
41 134 109244100
77 135 634218152
96 136 741122711
16 137 234536588
3 138 740605129
91 139 820155054
24 140 295606544
127 141 244149236
34 142 136391099
36 143 342288765
60 144 614128665
68 145 341709321
85 146 885069950
20 147 683771344
77 148 569498622
12 149 404998204
73 150 275298211
112 151 386570002
38 152 800948095
57 153 553464047
72 154 13608656
42 155 603349536
61 156 625744819
88 157 867214382
157 158 383410094
14 159 292966933
131 160 617183837
146 161 327207064
118 162 794029553
9 163 499974994
4 164 199378062
146 165 832546453
76 166 977588252
148 167 682056376
120 168 734606603
52 169 691827516
73 170 45648318
93 171 810704524
165 172 203392591
75 173 98728881
83 174 743209198
63 175 621041848
45 176 663726941
8 177 956509072
150 178 214331513
88 179 662804722
118 180 614297012
150 181 478562921
71 182 780982546
157 183 977282310
108 184 155731267
61 185 114250323
18 186 146417552
147 187 328316719
43 188 161875721
47 189 86549023
188 190 302932646
27 191 886160082
57 192 969961818
58 193 993541238
184 194 153950151
75 195 317418464
13 196 374039942
118 197 489807152
193 198 488556695
125 199 190232709
74 200 443024000
71 201 696854121
68 202 247486229
104 203 937112117
101 204 706015392
136 205 292022871
31 206 289310491
41 207 558925571
185 208 472709651
118 209 260236807
168 210 511384720
62 211 707778790
211 212 816713052
36 213 355222278
34 214 580904736
80 215 288975973
83 216 518391273
34 217 736126201
6 218 21326920
68 219 216968553
142 220 852565904
37 221 943450081
45 222 941197971
43 223 680929542
99 224 643877637
66 225 850743565
133 226 136343509
59 227 584218113
125 228 16971791
140 229 704522287
47 230 341357533
99 231 379239382
61 232 946523075
178 233 331646433
68 234 919972241
68 235 227499241
101 236 351302371
125 237 453808857
166 238 642736856
82 239 545755956
236 240 641486411
3 241 383381276
212 242 950666415
132 243 576491252
83 244 358585132
21 245 62213757
236 246 212251951
108 247 459731183
78 248 857741376
174 249 253805472
229 250 376001329
1 251 932793134
67 252 158102083
103 253 866887408
247 254 572162017
188 255 42997060
140 256 933891666
218 257 16383835
70 258 865938009
7 259 332081710
96 260 133939391
74 261 92413455
91 262 48359079
18 263 474893938
237 264 722680606
175 265 105884380
19 266 316106217
146 267 201669614
175 268 452052340
52 269 323630811
200 270 723362454
173 271 178704156
170 272 133860833
249 273 38325874
116 274 971498345
262 275 199145752
120 276 772607499
40 277 684249784
199 278 64980910
188 279 595608694
85 280 464053643
24 281 7450915
262 282 376716068
245 283 395166809
29 284 54686937
186 285 795315491
28 286 207620702
33 287 796752250
194 288 635691062
165 289 891541791
194 290 164781745
268 291 641362459
23 292 760559628
73 293 169805660
104 294 439686500
212 295 148567476
1 296 86208752
74 297 915363148
132 298 547837889
150 299 93763286
105 300 693037494
39 301 449331473
46 302 286379239
31 303 555226854
81 304 247188776
251 305 644386639
149 306 443225927
113 307 398733855
264 308 640114810
158 309 498644365
288 310 150941988
72 311 838458113
154 312 915683699
307 313 250076852
165 314 35160235
314 315 212678991
70 316 649288855
7 317 424629724
261 318 607626226
285 319 460158476
161 320 836805444
214 321 235014879
106 322 694399725
236 323 893646994
58 324 270738303
52 325 379053491
224 326 496940725
142 327 83529297
196 328 81449171
33 329 512910497
328 330 570026461
281 331 679016349
82 332 258974516
268 333 777291674
60 334 803501545
110 335 355160592
195 336 707100176
128 337 650558564
60 338 262835778
272 339 398714725
97 340 426367492
315 341 909396485
127 342 107913675
83 343 103702234
268 344 305428189
255 345 285913134
11 346 609802138
297 347 739097869
333 348 732559581
51 349 738216112
224 350 922954444
265 351 437305398
255 352 449658669
86 353 369911590
236 354 212340583
22 355 367690197
353 356 89348393
124 357 859856158
292 358 532215075
19 359 96324803
234 360 132463059
298 361 949655007
242 362 689801325
344 363 797495926
142 364 630961747
253 365 822499644
277 366 568873778
105 367 784825351
10 368 255078227
123 369 888760901
212 370 923700434
245 371 412607512
192 372 435872105
335 373 134503993
24 374 261325024
71 375 924898214
121 376 272573058
32 377 379463646
343 378 864830503
208 379 925946261
226 380 688210437
36 381 752921038
380 382 371358242
107 383 241686927
168 384 8557280
77 385 395730054
179 386 548294794
193 387 665986843
213 388 557456954
192 389 562896741
284 390 422647200
346 391 237491016
203 392 843114603
88 393 75733802
327 394 42888340
252 395 286421292
223 396 171451632
341 397 160341642
26 398 707459007
236 399 520451904
210 400 47956092
19 401 158621860
296 402 815221062
65 403 605079225
223 404 294319634
384 405 594296220
14 406 157430024
9 407 836029113
207 408 662270572
406 409 553302396
358 410 787529665
210 411 73595593
4 412 592129462
354 413 776453233
33 414 673914444
387 415 904557017
314 416 579439022
9 417 252681149
121 418 310499513
401 419 842915966
176 420 122416521
354 421 583583025
48 422 498391860
62 423 215845074
285 424 755726716
300 425 220101945
313 426 708747739
185 427 611369086
352 428 170235277
293 429 353535782
173 430 94922077
2 431 266233123
263 432 268557259
118 433 679933630
60 434 389032965
277 435 666823478
339 436 270366391
249 437 830214063
433 438 654930234
295 439 738591225
109 440 340563074
301 441 910814726
195 442 982531039
383 443 860037442
31 444 20026879
192 445 706997335
204 446 381661513
114 447 496048757
238 448 631535749
173 449 41463655
61 450 607387538
106 451 645680089
262 452 889064694
28 453 368981737
137 454 616451078
411 455 997873332
143 456 738544322
91 457 379728936
390 458 731259012
377 459 913772111
162 460 640400128
167 461 791303799
77 462 977435412
364 463 150699930
143 464 525724415
346 465 599342096
439 466 72419446
254 467 866852107
369 468 486890694
250 469 296526799
402 470 567919572
216 471 46654261
366 472 913837110
451 473 855471299
100 474 910093844
141 475 241950981
420 476 900353597
111 477 257904154
396 478 53759206
167 479 742489900
378 480 404422969
23 481 648906379
325 482 512333254
34 483 113375691
26 484 211352656
435 485 989534489
163 486 723989882
240 487 14762372
89 488 551549071
65 489 681538763
334 490 883722599
37 491 296519682
81 492 19937327
124 493 67037452
85 494 965933918
407 495 639436552
432 496 846604815
315 497 353492824
86 498 5327827
243 499 133072945
441 500 366482447