1000 1000
258248362 950191780 581889379 864890840 -263882150 466743691 843023569 216307627 -874999748 980071552 851606160 754898737 -376863306 -418707963 -398327137 349430851 -429162264 4187055 -352746204 344059252 -263707396 -529322809 665318878 -446470004 -944952471 -35111413 -910794429 581951269 558425364 -231332679 878787156 -330809921 -428624547 313192888 -613402729 307493303 -367547069 -917862808 -623682718 -242546817 -937791255 -919560205 -635131728 -462138209 -338268168 -33458865 887292643 232569569 970728191 -612937209 -570854827 -440462853 -142260017 -905535949 113067144 -234696136 -88131009 54789067 -800228515 -677189293 823456388 -921441359 -7999214 -752651807 244267881 378598058 554841496 876720812 460735250 931158778 -513309652 375460347 -988401427 -148441380 913322139 -474153242 818099756 653131134 758416327 641344299 -959806075 -959922148 -946602202 -249549740 -865458097 166464942 515754124 -101072754 -926229639 715525609 221737954 897226749 646600603 -933744908 -855425058 -256615164 444853150 551932790 -527377999 -241895247 335607921 -40687651 -866434900 199722846 810870969 899403591 725569604 481487077 405051077 336502283 -24652272 297761355 376580135 28745527 -951788385 363638391 -952273179 416482092 -884918011 -878502817 -15475947 336819943 -981276068 -516358992 403075036 -984184773 227025845 -299555462 420264369 699647846 458549291 -391611358 -488523453 444630744 808111489 -825136132 196550687 386197445 656350946 -545881883 -424783919 -515784974 751879472 951796216 512960553 652607439 167950959 560687375 -78394117 283032949 682184558 906129937 -527630756 553424842 -757712703 875444280 421756421 469313142 -571594829 -305462857 21477340 886954462 302925785 532953887 184101558 -36446374 707817756 -766831402 -797732576 216685054 -312713285 -222516495 700900080 -708317461 -418203927 66376986 944289978 749747033 -520419287 -281587786 -114703666 -985718377 -522941497 357665578 567706465 -280654200 85626211 -158020761 -958824705 514031382 536516382 62652635 253502196 -308041481 -551877125 -709879893 655512146 -991543017 -476711295 857779570 225142037 210575420 -512220573 -221441531 502257959 69575500 844935455 299064289 -328161115 -822967480 -982523497 557135219 -808685857 -652948642 -232682850 759020609 66397159 852943361 -546483800 107572454 219491095 990032582 -977258559 -674490357 -465492547 -529135684 -384370250 -957464049 -520678701 138918455 900315521 704463336 -797989773 -759388700 -664461842 704268186 310186801 -967010035 -144151172 982025686 -789977514 -274158317 391677258 -598663371 72893042 -988489240 -987126410 -860709799 864454121 -533610210 99379007 -63538432 -691061276 122120448 261971211 -156553822 592984765 877600962 -114017871 -927693936 -130964231 -361185997 629285753 71045997 -120574697 964823911 -372169465 -957871544 997813876 483679363 -975845857 -939647286 -937962601 268347753 -538310656 134930441 279858513 -525437066 126736994 -3171014 -59047275 -921367647 933290554 249891449 200752801 47778117 -906662373 -353746082 -222104569 -168163891 -428923665 646931201 470650112 -947121560 -429506450 -797408233 -982297649 198324085 -755279776 868032579 -465480199 -878609281 928385294 -403442800 389738472 -757409010 731487641 -477886663 -282846076 -289259013 518942323 658106649 -210626660 304749229 -239485549 990126141 -794956302 -293631570 -511103588 -17060870 538204539 59972747 -517613317 -138628997 112851187 52880233 63962771 -16930110 -896279330 308682995 -296381179 -361759529 430073714 -515479533 234797671 -327671462 -272888543 -181198336 194441875 444265382 529542651 -434099450 -45111617 -828567657 870649779 715402834 -985925163 -924306523 -725712383 -497028751 -88851041 812492156 562943996 393535642 -473620488 -471688465 -701067773 590342283 511381425 -597347102 -248458370 -932483402 40893369 -965868304 -447962934 -871792607 -293539766 279148523 -52990943 900902109 -424069743 -670931939 -680680989 530818641 -499499596 -957514858 98737827 -485424759 -881821381 373025444 17546490 -118156069 38033953 -566993162 -872104075 564413465 -38681627 -573171847 7272100 -674783850 -170518949 758813730 -607267251 870374420 792945426 -55230185 998581813 -648077988 -923565310 -201892777 -894659527 -347635052 127175284 -575340516 -964300059 627675688 -532855374 134437768 -857749070 -562160403 -640020435 12313772 319683528 398013518 445320611 447579454 -185056665 -740844664 874407607 822215435 -415628513 -443594990 433545517 -22895764 -720704218 79007295 921874051 -869606052 430929307 998308741 -71498829 536269780 -496809959 -944323545 960929264 -461110018 535868495 -719409758 673327751 530635777 -281570161 -966692684 -604534098 -961886632 283837186 840786513 338209174 -901219479 -900058151 65133133 773512308 -463170312 621538143 59574177 513933924 900833925 -861418528 288324327 -968772127 422027131 139149421 -187754604 -189186737 642339462 -279561797 -375741121 -966254203 -891176949 -95150879 707073548 639458828 623278960 592897216 -965075270 513908680 -270749246 728227595 -295365794 -319452373 680685797 769767339 -693423713 -929968163 243821834 366150464 583965762 -2827888 357248288 -275193559 -119083663 -368208229 863955862 693161734 442605034 358811677 -733883711 -933136087 392557474 -625060660 -175770614 -47852626 -985601831 -699975302 -602439058 901839251 813933379 126811696 482583199 -628916063 807359323 15785348 -859148723 -886064390 85817185 237189463 332602426 -477700701 -913122073 -457632934 247105741 -32205735 174158837 -36422045 -486527649 -530719777 -825094016 -220411360 -611339512 567463458 154527981 212889874 -627872816 21442502 512914572 -230311874 -224201895 179364303 896499822 -889102344 550448241 556375497 126683004 543815870 522827459 -934983458 -366478315 -292053763 -412684159 -279600387 250313303 834421582 688193878 -723011508 -349484110 -945817419 -253731285 -174578126 -166228779 134929203 -754598315 988299202 -799664571 -382471131 -137741944 713250002 387216996 638056162 -254869343 136233170 748953818 -851904750 -454874980 -271846825 691911120 -932047521 -206830283 -822050842 -371584931 380485558 -101651229 878728372 67423493 -560940999 -991766783 717939383 -506758418 -245498068 -604122391 327012803 889431136 -358720706 167828358 -910233435 258808164 -969913586 655532919 -501458488 520658928 -746820071 634774682 122129099 -598724821 -967583946 850282274 -906813700 -899631466 -504031657 -876348190 -418700045 876453901 22000581 -687455321 -203606254 461059582 -679222104 -633150519 954301164 75279829 -237272909 133830319 -182772683 404006385 -845824971 -240489766 -484669099 -963222204 -732440494 13872413 557436724 -479260565 -498836552 -467917825 -77985386 -466420498 -765119199 -132282734 -513535612 -269150856 -8630924 67764343 -540180602 -986630343 380309023 256213144 326945591 701086919 623062626 133763107 -371116900 -761693931 -879890221 446110417 642312454 -725715192 -941862996 -989840292 -688937396 -674303490 24032121 868499329 -153564055 525195569 -746902144 768450559 -941224928 -512021342 -511315822 -602244188 218827802 480053254 465520156 678647200 345939264 -301654469 -212623303 -474598793 -748051198 -737044325 659164315 -119168097 -498738256 779274094 -820541328 -856425802 -946441098 -762404324 -993749742 -782862141 -436707814 30282380 -914362812 409728131 -592005699 -808748604 30695043 -680714275 -320769946 519379221 -282958462 898057857 -148051173 -964921954 429221409 -949595557 -266576423 -930885542 -424194349 -14627621 -667929867 -912513682 866204282 -166668123 866760412 -954337045 -170577572 772835666 -864225017 -164327314 989973525 -300932830 865955066 928127065 -891204699 -873534280 -880621538 -7993304 -554248555 -348875132 -636097731 162792983 -598300923 215851097 197871029 830920487 266255540 931294606 900034945 842061191 -230816662 -915378569 929547509 -512096028 -82046692 648824273 -613916721 747375736 274176292 -478141737 -564435225 116666169 220925433 -845963807 -102690413 182237086 -719498087 -130795599 -973239865 -273746641 520329269 -609337596 889046342 922028347 606513501 -60566276 605465186 -274714606 -276755318 358016483 -580137063 492428020 442637914 -798073201 980331993 -786892425 850751072 -781068376 960483311 -22556284 -259210113 -751435562 -905890114 961715320 -597399368 -156064175 -3531241 -316897455 713140226 23228894 409355904 85985847 413891298 150918599 -139469454 -127078848 -909647677 -681487916 598206546 -333886643 676528568 -981930517 -988942270 -28317166 -927487366 991389723 184790409 923263707 -937162301 -2209927 -246776225 -196372413 246354511 -300149987 -382140741 648955143 543785838 614328018 -815425959 109442416 -509926736 593929945 -952055384 903964563 -402635104 -91524838 -370597933 -459766429 226987247 -919875035 206346929 -243967833 -901805552 217404659 727715001 -976776565 61310734 -234978237 946487142 124148433 762811836 -447772731 927776020 -138317301 252077283 -601848368 -636845805 -351620527 -987520350 -452271764 757821890 -644930733 -858341819 805766506 -888449818 -408460570 -433241980 -259047751 131773001 793745267 -178922786 -809363718 -597706214 -228211986 408040941 -869991212 -204988551 -678131973 -252453097 -405985057 446016461 -637124909 146242213 226308833 224557790 -749164152 624460465 587711985 -100784679 489456468 -864559779 -490446437 844525735 -870385245 -832163579 956075917 -426329463 -265405558 -450455482 705443538 -619143939 370621732 896079821 -216850152 -857590254 156637114 -234325012 -210062452 478505142 513221891 383952491 -222962045 876096982 -617288944 -996653212 -46828876 -366453096 480323606 -606600538 532762226 -177703574 -618643965 -957684211 -480661487 -636512858 -937331437 -672069218 -62842321 -202736995 -122524700 -504882430 178119066 -899386616 -756286257 961268914 -904460518 400350857 -420539746 -114522970 -268627649 -907317855 -878054126 508410306 821295479 -495343070 364273447 -373017044 138203835 -302886595 20382418 -476517587 519409831 401738453 -581685446 -961251656 765225596 -519016883 -780804522 -445100373 278246122 96670778 50017197 -691118459 197284162 293730940 -877333193 292823644 -453401850 -297872938 -969182973 277970501 -352674441 -847237099 -361102840 -678862609 -342580169 -996829393 -51879653 795623666 -447199636 968502765 -828377569 -927789805 222757570 -410063014 963474891 -159500482 70920103 -964813279 395399146 -798317422 131857499 -702067305 -489435881 -818341987 591663636 -366769074 474481657 -861738214 335357988 505298684 268748639 982683548 658061585 907645799 -843662709 -832002231 763332758 104457638 963621435 -831350526 -74523245
22 868
206 678
197 913
309 634
695 887
390 485
358 498
26 285
164 508
192 625
156 173
130 307
816 899
418 454
686 892
209 905
887 914
178 462
435 771
129 164
9 648
367 518
498 896
3 5
411 627
548 566
29 152
225 967
279 642
421 965
533 981
221 798
219 683
653 976
139 805
133 165
138 651
531 635
533 898
308 991
512 891
226 663
450 919
198 629
49 443
327 514
86 382
125 600
100 768
605 924
89 590
79 89
739 971
66 988
56 504
367 648
873 946
29 217
657 674
414 468
58 279
439 794
270 364
390 484
346 369
310 407
435 495
389 525
454 466
321 513
160 861
159 687
384 715
375 409
140 723
780 876
418 669
570 781
939 960
616 659
23 305
91 321
61 869
616 686
480 866
358 726
396 639
236 374
462 610
185 782
657 749
518 964
534 677
299 967
266 845
501 626
288 298
509 592
358 559
194 223
38 904
28 300
299 536
401 761
497 534
598 945
190 260
115 218
145 765
185 989
31 810
318 490
433 459
178 816
724 991
380 390
41 627
407 925
159 928
425 685
629 692
233 374
241 488
385 450
253 634
283 726
567 795
253 952
130 999
341 420
809 853
479 720
202 478
129 403
440 636
679 905
278 420
660 911
712 766
370 397
122 346
140 652
688 955
38 745
84 164
288 378
325 449
118 526
873 926
6 913
263 312
731 943
540 853
657 743
139 916
261 378
29 612
299 753
336 849
419 688
12 417
59 688
176 217
142 213
48 571
406 711
348 833
442 724
536 552
733 819
110 674
80 285
184 491
826 935
32 974
395 596
390 654
83 606
182 647
99 229
217 856
401 940
555 733
125 458
209 268
276 293
355 670
160 929
215 890
273 337
188 285
668 929
102 938
119 886
100 984
317 700
191 991
69 745
545 723
202 342
477 753
634 775
184 562
425 934
128 623
315 698
717 907
196 595
480 818
667 917
718 815
5 585
6 708
101 782
550 654
123 655
108 130
429 665
21 714
90 148
139 688
594 814
408 855
24 142
160 887
53 292
229 877
57 936
234 509
135 717
162 191
643 789
217 298
308 318
283 749
817 970
630 887
93 916
37 57
116 275
407 568
679 796
635 735
220 731
595 799
355 756
341 495
398 638
57 64
307 346
157 475
43 315
104 582
135 492
602 990
118 557
361 796
347 352
434 882
476 567
273 584
583 924
332 767
830 913
571 741
527 897
45 194
292 500
426 775
343 765
380 460
321 740
25 607
86 840
652 810
315 394
249 276
43 317
230 933
224 673
751 800
197 569
860 944
696 718
39 638
17 482
155 850
108 457
193 531
296 340
197 963
472 733
402 563
495 866
90 983
134 167
88 840
135 330
378 947
852 936
416 686
304 617
192 411
425 722
73 604
61 800
35 146
623 949
489 899
444 881
578 962
14 769
49 696
348 903
73 106
635 840
143 939
334 456
233 349
407 952
305 820
103 691
726 965
639 863
434 566
95 495
108 748
263 796
155 517
227 495
130 974
117 418
68 226
768 802
209 458
720 762
174 380
344 804
442 899
558 816
4 228
310 975
111 924
122 618
440 617
766 844
98 614
517 882
35 839
284 296
3 595
409 974
212 529
669 779
5 226
232 595
229 904
206 692
680 828
309 619
296 504
384 745
117 617
261 955
544 652
598 602
10 899
572 779
221 240
226 557
151 818
398 809
15 407
234 441
694 749
204 341
588 605
73 437
204 697
207 380
592 981
805 842
343 376
620 915
177 967
140 784
679 949
85 182
315 622
360 670
723 874
52 679
488 813
16 751
184 482
127 575
731 815
157 969
458 940
71 424
468 563
147 208
741 863
177 583
253 714
788 888
478 939
290 466
426 569
657 961
231 402
87 216
313 407
372 770
347 795
194 814
357 753
312 571
845 895
558 747
499 986
346 976
163 924
265 349
83 921
309 485
504 747
700 816
154 424
586 852
131 218
17 926
329 883
496 727
575 594
73 636
333 579
48 854
312 496
554 578
584 862
414 439
114 960
113 255
192 537
106 316
322 333
383 556
230 661
235 634
621 823
659 753
706 954
606 801
159 369
730 952
144 372
391 683
609 997
145 796
463 540
213 602
795 984
768 807
213 753
387 393
51 373
491 678
448 756
124 478
560 958
428 681
170 703
311 363
510 518
57 807
760 973
269 767
95 388
659 926
318 492
45 864
369 887
476 542
334 371
643 952
379 930
323 984
685 900
417 646
547 804
519 825
445 563
637 657
562 832
315 675
232 711
538 600
431 949
282 427
154 378
276 435
598 756
419 655
416 635
181 423
220 247
51 782
39 691
791 874
105 601
184 548
168 438
116 783
209 220
725 750
25 939
160 694
930 975
701 961
345 475
141 564
543 722
698 764
488 581
533 990
889 944
463 716
678 850
579 898
59 680
349 622
56 133
30 42
62 94
407 990
482 569
322 642
19 24
757 957
746 858
154 489
205 635
312 616
54 546
464 561
225 535
281 812
206 667
662 729
4 651
135 571
485 808
212 861
321 827
36 817
66 657
52 189
805 861
267 716
350 628
82 927
162 246
559 829
220 451
453 909
223 395
24 60
202 235
380 920
88 555
416 973
604 744
376 957
91 760
223 462
656 719
232 388
298 901
60 703
517 968
92 156
179 714
151 916
422 765
295 320
509 710
604 644
19 666
425 560
134 462
532 886
142 273
42 763
175 570
439 745
494 900
208 882
384 430
123 194
417 805
665 865
479 508
144 620
532 879
340 568
665 806
223 806
430 985
200 352
159 296
653 790
23 547
860 976
406 982
169 562
386 750
226 580
845 893
75 123
376 995
393 814
36 800
229 550
21 101
531 580
396 721
183 942
394 743
500 917
438 727
61 829
638 823
67 408
483 835
190 562
355 477
276 954
391 856
763 856
788 956
645 704
508 828
603 645
573 914
300 454
351 515
173 480
504 887
338 591
132 721
197 900
205 487
229 824
32 60
368 991
635 819
71 678
715 814
632 739
438 980
330 390
869 952
455 854
445 755
145 828
44 576
376 414
200 600
642 660
583 632
379 753
449 619
430 784
414 515
522 847
851 911
154 176
131 382
886 960
104 826
713 753
88 499
99 167
639 808
110 573
488 792
325 762
107 288
154 897
419 520
722 1000
528 681
812 875
834 909
49 86
113 290
190 788
356 552
238 543
347 516
115 659
186 440
473 772
668 898
417 979
330 438
471 490
364 857
634 765
549 682
190 202
146 392
330 697
99 567
591 966
706 914
451 624
497 747
276 394
254 415
162 204
583 651
674 792
307 366
908 914
110 340
104 837
501 785
886 951
351 476
616 917
181 892
29 67
342 639
405 422
935 947
529 608
585 634
320 950
228 940
216 632
671 689
468 541
353 455
491 805
759 829
361 773
191 651
390 641
163 532
397 478
98 356
358 682
30 989
281 984
199 609
649 912
221 731
189 675
31 436
264 831
603 790
792 976
365 793
676 784
180 880
505 977
215 535
10 524
596 993
204 804
67 543
763 852
392 797
232 789
422 620
211 847
574 823
2 719
137 539
746 770
251 316
203 746
756 817
78 412
233 748
643 967
170 299
405 447
194 561
31 982
165 877
545 738
51 546
456 942
35 202
350 711
457 804
552 620
564 629
383 663
349 861
305 511
62 518
430 958
607 988
411 771
216 955
508 619
316 853
560 887
622 869
24 588
430 492
993 995
377 472
656 685
77 312
195 946
373 504
331 375
137 843
59 101
444 961
648 677
588 628
496 886
209 473
639 871
865 964
788 983
593 990
472 669
18 302
26 614
340 522
357 716
476 809
271 774
769 802
396 918
741 803
243 950
113 276
591 940
922 977
569 730
201 912
565 589
219 554
92 942
650 893
721 807
459 933
343 579
86 261
827 975
63 217
690 776
67 682
633 658
362 988
251 579
519 915
485 815
73 109
317 576
734 758
216 389
18 732
104 795
121 992
282 406
409 689
370 448
432 475
380 814
145 310
59 65
231 828
543 900
339 470
97 569
556 957
664 925
458 688
31 380
661 930
619 789
69 588
340 895
19 719
163 709
28 773
222 856
116 355
107 694
675 938
142 493
632 805
417 671
615 797
54 544
809 842
514 878
781 854
124 799
572 832
952 961
534 956
311 807
2 265
4 939
145 940
783 923
301 551
593 915
347 998
459 508
191 972
385 971
508 825
749 769
82 692
647 700
858 967
957 968
122 312
258 413
40 808
109 335
280 591
23 289
277 833
468 796
157 532
333 790
392 559
81 83
132 992
81 958
38 989
278 463
535 701
861 875
562 575
517 969
343 841
469 805
528 601
684 936
484 726
368 875
449 636
957 979
38 932
273 936
427 565
87 479
100 961
26 339
307 522
714 894
2 698
183 529
470 650
134 212
547 579
8 534
317 379
512 663
706 800
132 935
21 364
815 962
301 333
207 840
733 959
920 960
454 783
432 488
51 276
822 917
925 982
708 712
219 593
298 374
18 660
429 734
32 390
365 548
42 740
1 923
194 824
606 960
648 800
390 923
306 850
96 183