500 500
332339080 254234032 459516135 72415330 730947552 698946728 910621378 48113383 86199008 130413142 967528151 903382683 510703501 369801877 727606922 633744706 528905373 729234438 348408800 582305636 44625228 511494194 62541117 227023659 777441812 497726233 391877737 335603500 567255517 419309042 850892409 935320097 590398672 615399986 626362022 972839592 662674678 674048801 447825820 814807334 897768000 754179587 644837732 34025163 69038177 185408248 441312316 915672370 978921700 252842601 814217038 220638296 82942298 954933188 674758462 34328323 919516195 869227226 69893211 874060652 268619314 67284216 590714944 673709683 348428301 78996891 288522525 894162873 529872434 838890538 734168845 35649619 57901150 439739146 563148170 499279462 241745749 736689002 321462078 739821517 363370248 596720143 996932162 954069562 997800574 668929304 674661789 725711158 180286478 86357695 812560935 560451746 794602590 595468181 578794902 192104676 720004717 113233732 104906358 236672579 37958172 942286348 359382883 759131113 143172099 473484622 968952597 87594475 585883653 299525987 133894549 15541842 260318353 502310426 393055455 680057791 504676432 927592777 831123877 588400979 378629619 979908015 95152549 138587454 508514524 26819288 560227865 144297565 491177738 952342288 756590881 68663798 23677475 805747750 848478584 867412101 877700764 814861965 458670095 988904209 45704314 286570421 249016800 528690848 907415426 71286337 792116032 998315186 422739461 625819934 543873376 279793579 540931733 122284227 439227052 993881714 899344314 125749701 960313517 772366029 8922691 346519153 496129199 134847053 100747080 686914170 250131565 287815950 5332948 371256561 758125624 411210508 75708931 987505301 28707461 515437297 711724721 75513822 475247507 368716214 35514635 552132060 792909028 999351700 329612261 723616656 478795770 451397653 532587622 748233258 261755809 141007435 853387579 464373244 484478812 188831558 896785806 772353580 282609187 789743876 159562832 264466131 846790591 472715648 748254557 521339841 120797918 525830994 364089380 352521842 85184268 443948285 740327277 147902205 570090429 675411715 125475592 514661440 417085414 263892676 947884791 563218689 390455810 329264686 887906430 282317126 846052318 727609876 857064423 505077808 380828137 445167696 305555007 852185970 29750139 722105395 134042981 103670612 838848192 230217495 237077552 304443083 783697111 101784862 207047146 40741858 462187046 356447873 715169745 347589284 150104188 550809234 910213491 402812050 594283005 990750874 158484215 249068376 621954317 887600737 44829375 459162860 662578576 14013655 741236694 890066954 466031075 846680454 617824379 627554987 718226047 717775630 187307821 198546396 586352493 436188636 348486175 592576566 4998852 765157430 475797063 199436490 372538795 815861680 156328996 382599113 581156841 779678164 506727783 61045301 48521531 854374763 75906765 307049122 302492597 147800447 387934255 926686431 960627125 415255176 496984457 540854779 357181517 506519702 371440028 421269246 899775698 903045902 915914658 173304757 398705321 580194582 604780247 202861820 37930763 228109538 694635332 586768482 509449893 690214929 721816170 810571720 974358653 999675830 878629338 74647723 386344637 370769475 51170338 451590816 322155486 7806011 454778192 118630832 52458484 636466179 83288515 36202560 256630918 645854825 926633700 581806002 802094208 427313432 813052288 476484797 146103514 575811423 549189123 842907619 190186876 729291352 988779730 398684610 410137124 135201340 378859451 221652327 731107891 327411527 1057277 869039205 884883258 753963445 936451413 753473311 982564889 261014600 579792220 558875915 294333286 237677243 881451183 453425871 724995407 526350711 148318832 380956111 449461578 792562675 638341508 317666028 992530407 848875373 855780833 806114271 97643528 998045071 341312049 846128112 349322792 818451201 260790447 48957035 120038656 6819416 151692770 175692492 938787690 992853714 334544618 362260294 110540260 893568740 513566973 4611075 416687812 942750198 193951942 476804960 297709418 832451157 17162633 692422733 263552380 604348283 490481890 670896564 345824843 696913688 758588159 727754702 685757271 506887210 779601911 264447583 171627467 123946543 241148114 850784976 884673790 637356033 88652520 778435992 619582848 415850445 116207550 658787320 715735462 79013392 42178127 124229277 845444758 228102987 284525651 199060758 591048164 806638406 497778358 359862042 568606427 599742872 57442913 795281312 138775153 526873212 584140485 188439184 126838282 722196114 283012117 498060398 514983801 224341958 711348705 385056573 876431190 77522834 265555301 553373220 515813687 411651222 966805352 162137704 196725009 192836020 934911609 712426390 62652216 507471705 915190135 179425291 594272709 479490359 540929732 962463334 758751045 326942034 282035933 949737916 786362261 727770576 818779915 607210877 658480218 66950700 245375399 439477851 159027217
1 500
499 500
202 297
315 494
331 487
415 457
69 333
225 476
363 398
157 167
257 271
358 404
466 499
14 312
219 319
145 374
191 437
242 352
27 53
201 484
498 500
497 498
182 492
32 281
327 427
28 357
253 369
355 427
272 363
305 413
435 436
66 229
152 457
103 382
368 382
166 286
394 396
104 393
443 473
202 417
13 361
181 302
149 382
423 484
52 441
215 312
222 462
259 380
232 429
288 300
335 382
402 476
10 410
307 320
11 86
191 334
374 425
311 356
77 229
91 321
438 491
370 379
62 95
143 482
145 199
400 423
142 324
129 295
71 140
473 497
224 330
232 346
322 452
113 476
28 413
466 497
409 440
71 164
384 476
239 249
197 449
99 484
118 383
291 370
251 370
444 497
243 309
245 478
56 256
378 418
281 341
208 371
362 446
10 387
127 184
227 245
282 480
472 481
163 418
418 451
307 448
129 221
97 203
57 95
185 397
269 458
450 485
305 461
52 121
10 338
45 96
57 276
77 165
429 459
495 498
498 500
458 477
22 215
282 333
262 330
251 386
444 492
249 389
302 389
399 426
18 106
239 306
167 399
269 294
38 323
207 446
462 486
247 405
81 337
169 187
484 492
315 382
228 322
286 293
323 355
364 429
368 439
327 469
151 158
61 431
125 457
217 237
134 190
105 244
273 393
261 282
378 403
420 436
383 403
358 468
81 240
9 59
48 395
211 324
233 376
396 433
11 407
294 400
403 482
164 222
163 276
326 472
306 389
194 403
459 460
351 370
106 138
411 426
258 388
161 373
156 163
127 221
449 470
227 408
128 498
405 422
466 478
428 477
19 315
231 476
30 167
468 476
369 483
245 389
412 416
66 355
58 392
368 465
455 475
489 500
230 379
457 483
25 27
255 437
36 63
232 458
112 219
233 362
40 196
7 202
418 445
251 440
370 492
386 442
73 335
265 459
32 500
304 320
38 226
368 470
81 494
322 333
455 475
434 466
280 288
134 226
75 443
262 299
200 326
83 250
358 430
497 499
180 325
258 481
415 428
329 358
458 499
142 156
208 416
423 447
39 56
89 488
209 235
160 423
149 206
56 452
140 176
213 300
265 498
133 135
107 433
12 106
447 487
470 480
435 497
47 169
361 374
265 307
422 473
9 261
428 465
7 112
94 477
415 457
435 466
412 473
490 500
50 56
241 409
40 447
135 441
64 441
349 491
189 496
129 305
17 197
188 284
81 105
270 427
116 484
261 321
249 261
1 94
130 289
116 380
270 387
24 431
357 422
470 496
484 489
43 300
40 356
368 421
36 435
62 106
126 381
137 399
281 410
481 499
156 457
393 473
152 229
64 163
206 351
50 195
461 488
70 348
445 472
464 465
188 299
280 397
420 474
188 346
253 268
244 285
255 494
361 456
206 324
27 161
142 164
66 500
132 493
43 187
55 316
255 467
387 421
448 454
307 423
79 344
354 459
32 418
278 377
57 433
225 264
375 409
393 481
479 486
124 436
425 433
453 500
419 497
102 170
94 326
451 465
122 493
453 490
137 465
221 391
342 463
374 474
16 265
471 494
29 245
242 258
322 342
398 452
197 492
402 460
116 209
124 162
187 378
23 121
284 384
280 455
85 210
307 491
47 193
81 355
116 462
228 398
406 478
388 459
150 486
297 313
239 393
401 448
435 497
430 481
78 159
269 393
449 480
436 497
353 382
363 484
143 322
318 425
227 299
324 447
124 129
33 379
413 483
366 401
281 428
204 372
159 449
172 340
200 271
308 450
372 405
242 259
150 274
113 416
435 445
343 398
475 490
392 481
221 292
445 478
330 347
376 380
45 88
84 243
103 391
198 417
49 245
246 477
330 418
138 250
409 478
151 465
355 360
237 372
97 338
492 497
239 335
256 398
379 412
116 338
247 359
442 491
265 318
474 476
360 444
232 486
457 483
72 79
440 490
474 490
346 380
442 490
454 472
483 486
308 415
162 459
35 378
262 284
266 347
318 447
341 479
474 484
129 331
433 453
90 378
59 477
141 415
270 412
81 493
27 246
222 469
145 438
158 193
76 229
189 447
400 500
30 226
406 459
319 329
288 372
67 430
274 294
55 104
132 369
161 260
156 229
134 491
410 481
298 433
387 425
27 189
216 292
8 115
145 347
199 374
246 436
388 488
197 260
20 474
427 488
294 436
434 463
37 260
499 500
77 201
419 495
191 354
393 416
468 470
51 350
87 470
23 24
466 487
351 445
462 488
118 300
358 417