1000 1000
687369942 -832050513 -544115590 -206977562 770327583 441399561 196708888 642437400 -830414983 382745652 86050748 403029059 -114766344 -136318756 -167621137 803674552 -290363595 -275979527 -281187813 158386781 44058337 -334787235 -443479832 -748900323 65822104 -925742544 -719864363 889648863 -405024368 -948987821 -905176492 -865138074 -928521982 -596775729 -72115636 841805601 844623832 -875406748 336759353 -985791150 359855256 -724673546 269754261 -902394736 139007698 -897866876 901279817 848644103 -321330051 -527391644 -140452764 722728287 137821121 416067404 973827964 -943840423 490324860 -893520047 945808441 -914699508 -989991516 893148301 -927321230 -918513498 -851111076 563134 923292103 993512757 -22327262 112567808 860237959 -809955654 387894262 -17491428 -712350389 -620581688 -62841951 -958554220 -919421232 615827998 -485945864 -59873996 191072637 651875258 -791290239 17416953 708034835 699034621 123896906 506359628 636851466 133905390 252024282 709530236 215391892 400913206 -437390277 -8799653 246942315 540282461 -896231844 -40303374 730326808 344178770 942205199 -982023581 723597083 -268120400 -940577801 804175851 -799776050 -574007313 -403181793 391296588 -922132055 -194472032 -738770107 638419133 -642921058 385126800 -2704887 993930408 -628451458 -898164253 555976996 586940435 502748954 -881413281 -569342866 -397792379 511385533 -613058358 561904248 94228693 731120413 356625799 -35278536 307233848 -911494601 -123339985 -36073949 -858754299 302652702 560744258 532542289 233037000 -781211421 793772183 -276027515 -424132479 31415335 721267598 -577685719 402963877 823103346 978291277 -157579336 178368652 949394349 273077799 780576273 313296234 660019441 194996873 -739958721 243656206 -595860976 224762743 -596593594 -654839225 -898577242 367332457 -513593523 256591812 -219406932 -981051234 -657854836 -618353 665237301 66117649 575249168 -450831012 -360098400 997563449 952132866 -684478702 828371078 -352930118 493889950 630281779 920147681 126982575 -203905635 432683475 -825504199 56135644 -471143967 -421365175 -866585261 -67737560 -76204399 -912646151 -847888751 410202078 343945662 -67295683 281667196 686090826 932085964 -200579150 -395275172 359851484 348589838 244626428 209931285 153239056 560147726 -109181284 800308939 -93445972 -626383153 572972972 -966463397 169711213 -141827201 -939451244 -921636791 387028833 -360816418 -788222051 -828192375 562979183 -700868202 -676081126 -174302387 643077460 256623192 -892635191 181684639 41225508 -240697989 786409467 -746406655 -892108150 -116447753 463524630 113647258 -703783675 -793140302 -233527451 202770353 -419523454 -808038126 88823308 750187759 50134673 149372065 828550968 -710320142 788555647 -959671083 -538512517 204051182 -808022932 -214593642 -970251205 835054528 -957970450 989629956 -130744481 -64228590 -398551680 -491818662 189364755 -438143478 391733585 -494594262 675503780 687949910 -287734564 -705507318 -256763385 292741982 -513545444 832059924 -104553907 536589229 -166051659 -423486586 826269088 -524979660 -530641317 -859727077 679071522 -338664249 -74320719 561336669 -651093368 -179774817 403482977 218162151 755996594 -995068703 726343490 -202122299 -580695829 -29406573 303283439 -905192048 -488940310 -984451124 -758183014 254296305 160807210 -271728458 -61127419 -943746696 -882622877 772820922 -514716930 943646211 -899642386 -45358247 -916080865 779429136 615977505 -137885232 193282157 964884137 682339952 -550718513 35562640 290852898 -693270864 -385577518 -911269401 -273966692 585015910 244530391 -326642388 -903924400 112595619 -84825402 202888257 -874080819 643446140 -858239161 -965311163 760823263 767098113 -480028093 556985827 867455728 474613661 493421314 499401216 -56892482 -791947566 -454800274 -239491993 890392386 -5518787 796070647 33761636 301210349 -736990518 -24991412 -972756343 848025392 -927944669 -446882379 796617344 184650950 468292219 -147978047 310570131 -35745289 -153700856 345258969 -422405673 -534086390 865230876 -865419846 -814114310 192360889 480517820 685286906 -864531593 688570254 -916997016 -251507234 431478993 77484197 -602920234 -682243019 -768789101 -339910752 292765569 -889029092 -639369008 364820900 -335911470 -990235312 -598011798 -867619251 -138213359 712558334 -50848187 708085786 -89666345 526746140 -973484252 -371919117 513842646 -787598562 820441773 -153123182 897688344 808426532 -612036576 980691329 -590564349 819442417 -89308122 -193484583 -862800601 141902777 466604665 282481320 252873686 827235657 -500181427 916962216 837000345 -98193225 901859317 -448696662 -533118539 -296472518 -888094524 377215116 -917210026 -861578776 -994704000 596632620 -649177338 678254125 -703974210 -898972641 339197009 -316010785 -918281312 748632660 -644052016 -155073082 -592335571 -654336265 986829696 874269094 628145056 92219734 554021103 -872036371 -138301698 243537800 -117713244 -383926029 794841139 349168218 319601454 906746615 -421100314 402391428 -954832160 -563287962 -148459599 -751493146 -885033837 147566191 -650465787 306679525 831555406 -716230747 -92171463 -959980257 128696172 315492967 -614316522 -31957780 42278413 -986171466 -939738046 -551184131 994308515 -225523392 692353669 -270888376 390550579 339711160 -921720158 -437331615 98974128 -490304120 965059814 -3341680 -53592081 -330883433 245165174 -86109566 816682758 594699388 -926913689 500754517 878468641 -19085151 540774260 -140318835 -851075832 926457738 827723385 191202581 792802625 740501691 640018450 639627492 -632505349 184888472 -778744532 758045231 -622884016 -847948338 -826770032 476090112 -338252457 -861710218 -674735216 608155462 -340077299 570429959 -625437752 -670878188 17645699 -552351440 829876329 -251369308 428563409 223166941 608311858 577487577 2141031 288551595 -378793490 -352539992 -118430361 -886258687 -860396147 249064290 298629785 -639140679 -140374127 675745769 -487089016 32855842 4352234 174658527 23661976 329617018 -364669659 683584678 -247436671 9892589 -987293510 770209028 457541149 695099171 -628643927 -261379090 -229217536 979667931 -831375161 772923495 120735878 -210168650 -727100144 -997694483 -96427337 -587496291 103886160 -945281200 -226636970 963512033 730464569 286274014 -151115773 -412666845 -686551107 872546204 916950174 -51220766 408647234 -477970145 958671824 273870076 -855244764 268729325 -178514401 -483888691 -992649764 592268063 -651704408 -971508573 217707910 469031470 -181677223 490607766 323853340 721895440 903111475 -719744148 776614240 -471009142 -903715763 359595162 815264872 -54831535 946928317 -871286234 -329768979 716394843 -69990648 -921121745 -909058949 -258802472 205264683 -764303713 -990073146 -973249718 -248192404 869793442 471534697 100103188 898284869 -458241041 -578348990 -430876001 -967633274 745504350 -856464209 787994553 -974239798 920150032 -830498237 -877955560 132261546 984766636 -80270743 -68293785 965996754 589960278 -499382589 -251477542 521354885 -408441538 489719987 -420864080 -172745251 352163193 -541597446 579062345 74472987 929937251 -468318115 -174725792 -675787438 -46667105 394398207 -790904360 -448646402 537933999 997090194 -570369848 310600383 -980891691 -595809056 -704621719 -996125055 323920201 227084496 822388051 -233603169 727701907 -576573138 -859731932 -828223279 913146849 -280596012 -968530 117826394 177806542 -569389833 -955184267 -39739855 -37707948 -129910059 284472708 915624948 -882995499 493568348 -680505102 654938500 343174894 -250874950 -181944765 362283204 153315995 113433516 218674501 -670247452 -806965636 -106421095 96149380 920736272 317005767 236417448 -907487007 82668968 955821437 -55939184 -946988286 -13855669 374670983 -902172553 946404477 -810520612 -32082612 83393537 -894895664 84921889 -570521763 -722884414 -407623259 772653132 26240636 410431976 -12547312 -967927017 -623618156 -941356459 -638174468 -430583791 -47777554 457974912 -657331167 -878255435 -453091288 -712301822 204413533 -644753499 231758994 257425247 341390833 -541053670 355252694 140311662 -351574282 -824313565 -923778449 -393953594 260608324 -494300212 -116838008 852985066 -869130728 909402628 115933394 118321960 941475612 492315239 176965502 -844182504 -938268552 -870812052 613792408 -743083367 -896551134 -986782528 -455385189 307862399 -631536026 776373806 -582196001 709854807 -912163512 773056693 -297317179 -263737794 948743128 -221095628 342308612 61867805 284604160 -922013044 -232630777 415473433 987389584 883302617 -613688255 781381548 228134208 563277247 937199044 142382008 544981548 403507804 399298641 648430414 416725277 943913453 -191190835 785189251 572803611 226613164 347560410 660640099 -147813790 -949756769 -750581343 -346554310 -318336045 591727269 715313495 966268115 669714225 -664800930 234257900 509620161 -928981960 620569646 143518062 299152248 36363245 -66766542 -705949391 -566138855 -810742385 693349250 -917708441 605982892 489779055 -256382923 243688495 -84900982 970230241 -556234743 -571744531 -325067197 -653475160 -322325874 328378494 28188795 -878082253 -103791659 -153026738 791631972 231407412 -918768837 153768486 302425452 554317161 -850197100 -545905948 -556803242 83036358 -251855339 -122942096 272293973 -705989736 -188134185 -269206783 783789319 555482892 974481712 -448595310 378229486 -729236679 -20339841 -946837711 -382711839 657334286 234057135 645476956 779252033 -869734523 -655033429 423400358 214189241 -721285914 -570314804 -630868955 833031247 -420511904 -176774903 -871255643 662524454 571369759 5802261 -212665220 865380023 817668077 518127997 501685694 225667321 345126062 -946909616 -543586841 615889383 -114733104 -637908199 -914306103 -604882466 596148936 731170853 -973114081 578930765 -923862576 450286277 -354363642 -792632138 879971473 14767403 -959600891 -688024079 837992501 -978340181 974500376 261878612 27462080 -385648492 -20225013 -302353491 -867520495 -666022967 923313831 330121919 -760416230 -767756658 -201472345 124850666 -405664857 -115778448 519968200 -956999568 -532091243 546854119 621931197 -603437466 -150343251 -879916092 -396069604 -417855426 134851311 -503154142 -105879504 -174639836 -481494323 -278862776 -912761224 545967757 335488732 -80469885 -903869381 320484589 253507149 -980555550 -496877139 493090919 -895795856 301650516 -529542063 -301460712 -961611580 990426137 -258460280 -493702823 389796608 -784012731 -97140289 -908030291 -663928823 506790108 -325885716 470922489 -996364034 568234780 -851200995 -625342005 -858111644 -911445866 920625752 477377088
250 372
30 751
174 891
319 670
607 759
179 959
96 679
57 357
68 948
126 766
50 528
846 967
182 972
538 841
106 946
708 978
8 669
195 458
128 250
9 865
86 823
187 534
543 853
800 942
707 963
277 842
109 595
642 688
567 880
24 532
509 825
731 846
189 868
40 118
668 904
105 126
78 664
930 990
559 931
81 521
710 990
450 714
304 401
91 222
622 633
246 809
328 483
350 654
45 516
535 819
300 944
377 992
960 981
518 658
264 739
253 390
103 448
54 751
496 856
488 973
470 570
648 952
302 897
653 765
346 472
646 651
642 767
374 726
32 975
238 243
770 984
569 842
439 895
294 671
390 643
133 859
564 780
162 813
433 815
577 779
227 286
404 776
149 221
130 195
532 724
301 432
60 273
221 498
519 892
791 908
275 886
119 450
280 406
262 839
190 446
83 969
416 744
487 988
244 968
182 776
43 613
102 428
237 649
599 755
540 741
15 425
15 133
226 773
487 764
210 611
28 579
444 644
130 674
269 783
449 965
396 492
176 929
518 593
192 824
272 715
284 638
491 651
69 122
423 886
385 555
447 935
315 442
378 988
512 572
20 608
4 476
405 511
179 456
274 354
545 999
282 420
262 535
656 932
330 706
237 893
90 691
171 404
133 900
56 743
411 703
75 887
58 938
588 643
393 916
743 941
712 812
24 346
308 973
303 354
13 246
455 539
289 709
421 858
608 953
18 828
655 902
64 256
191 898
651 935
165 943
677 977
53 654
626 674
27 360
724 928
625 818
178 265
388 526
485 685
692 864
698 855
110 765
308 761
8 411
172 594
353 623
358 500
174 675
386 983
263 552
109 528
432 639
792 958
378 828
421 794
648 691
118 808
758 878
115 117
60 640
344 640
140 682
356 701
665 683
216 741
202 297
729 744
192 887
38 569
715 831
341 405
458 831
212 588
678 687
56 326
695 738
21 771
186 721
127 850
219 755
52 418
513 772
132 963
169 399
465 883
223 351
181 870
32 433
120 718
463 527
395 552
222 415
322 407
487 800
242 609
19 26
142 645
776 890
288 457
691 944
646 753
266 974
179 297
298 758
220 367
177 761
398 771
445 528
14 156
244 764
255 614
141 251
30 756
26 212
321 670
774 902
167 967
99 497
816 856
146 182
76 322
198 294
719 821
227 642
187 886
793 990
483 499
44 606
69 864
817 885
71 742
60 658
589 756
556 756
701 964
39 937
23 583
93 588
582 755
319 941
661 819
669 734
129 143
275 358
443 549
243 290
865 900
349 806
8 904
561 971
850 957
361 979
300 432
71 186
742 881
479 699
402 564
368 544
692 994
240 901
436 495
653 882
230 395
458 754
18 486
442 724
436 867
650 772
735 842
188 968
583 666
336 666
385 581
231 272
378 484
166 863
744 978
372 818
275 326
477 811
552 644
604 863
375 987
74 512
51 568
41 503
58 716
296 838
69 795
172 919
134 552
529 689
229 506
253 554
132 729
716 776
633 671
619 990
45 501
44 965
84 552
467 619
494 656
267 288
537 724
627 811
500 670
251 508
112 357
804 841
840 872
824 968
542 957
443 939
809 838
360 903
369 922
331 767
24 949
54 100
216 485
78 507
67 585
424 757
696 912
616 888
583 783
325 711
505 539
347 615
343 517
59 616
237 741
382 612
689 787
63 525
2 141
69 383
139 725
773 844
51 459
185 660
370 393
283 861
227 475
569 981
39 991
184 579
131 917
171 191
55 253
56 696
78 393
470 476
569 671
242 619
481 901
155 873
16 622
155 200
136 842
185 768
303 526
657 763
219 953
273 827
558 874
681 950
508 952
520 771
12 179
490 659
264 644
238 884
11 38
437 853
173 557
51 389
151 859
430 707
456 885
13 54
86 759
62 314
85 594
124 581
422 448
64 134
17 417
301 780
89 407
931 984
372 645
856 981
39 522
285 977
338 924
34 989
655 776
95 721
27 91
538 844
329 448
601 864
253 346
752 995
694 978
34 338
15 349
193 871
53 829
199 328
167 540
294 361
194 455
14 284
209 481
173 280
126 537
234 496
378 490
71 337
371 468
761 816
305 385
686 789
134 885
117 652
424 477
945 969
284 958
116 604
166 776
54 396
891 901
288 631
380 624
53 847
165 994
663 730
470 700
519 603
936 987
254 711
198 815
98 679
282 507
24 214
410 961
77 662
364 851
230 292
697 988
333 429
91 861
63 682
142 933
78 284
537 919
733 788
86 819
183 592
452 748
615 861
692 708
523 558
166 407
139 746
214 567
75 79
9 493
108 151
392 425
580 695
280 367
366 779
313 537
309 989
60 276
767 849
723 967
676 725
167 889
454 471
549 733
94 528
393 988
169 244
175 379
658 863
541 993
375 430
306 684
418 717
618 959
277 836
341 863
353 581
29 823
34 762
723 914
115 207
802 901
283 631
497 976
288 516
15 490
147 297
50 714
215 360
50 332
24 988
340 913
604 941
163 989
54 885
254 612
154 352
413 634
388 784
131 424
256 972
552 790
470 839
266 684
198 949
86 537
350 972
876 927
390 642
267 696
275 521
626 659
72 674
611 810
459 741
585 714
64 374
618 885
564 883
113 569
6 183
506 649
355 524
432 996
698 914
43 540
570 702
244 517
127 773
405 583
220 341
635 649
266 714
520 629
440 500
682 741
389 445
187 799
264 970
146 177
19 541
68 589
242 936
184 366
63 940
300 634
280 948
268 993
213 787
712 973
226 713
22 745
101 283
716 820
252 318
245 623
312 858
211 451
248 746
168 662
467 685
295 964
415 914
308 979
53 280
43 278
787 992
300 444
70 471
159 673
140 755
349 647
67 209
151 666
318 954
638 679
137 973
903 953
238 260
290 881
891 923
882 920
62 571
483 677
41 188
155 533
154 942
360 881
32 362
25 316
701 703
305 837
27 258
617 739
869 972
760 906
177 894
307 993
22 747
140 789
209 296
502 672
449 904
810 862
238 935
477 636
293 782
671 824
391 915
287 611
545 886
131 722
67 721
438 468
88 226
648 959
630 873
149 321
362 533
483 820
952 959
244 807
92 630
266 482
544 553
445 781
166 449
521 912
232 349
319 340
298 926
151 318
279 467
471 812
180 305
131 983
616 789
707 726
770 992
189 666
633 896
344 446
150 357
216 382
57 556
52 335
205 370
484 485
188 307
295 367
612 629
227 850
417 575
538 933
473 566
203 461
1 457
156 607
709 724
340 766
279 391
100 483
112 584
299 966
612 890
18 853
592 867
8 431
364 441
7 898
100 188
819 997
327 452
161 955
50 294
680 926
36 377
148 162
312 480
553 798
443 815
35 406
681 836
122 394
291 551
91 480
298 743
87 194
41 976
25 354
631 686
73 704
218 359
220 670
49 370
491 575
184 980
865 877
167 623
70 338
817 913
7 160
466 598
201 442
906 990
27 818
522 889
99 247
91 671
139 269
40 843
223 981
174 210
439 692
776 832
96 113
624 944
103 410
221 303
203 562
372 560
448 588
245 687
47 335
667 709
100 825
806 861
322 386
15 113
198 429
240 542
184 293
165 395
738 945
49 499
299 609
239 870
115 408
277 806
801 985
472 626
84 684
431 757
69 797
850 869
461 994
286 391
644 907
681 940
81 644
295 438
41 307
449 533
773 809
574 606
430 793
199 228
113 981
534 984
205 777
122 383
125 665
660 759
31 791
27 599
36 872
321 912
205 694
712 819
13 318
157 392
747 942
384 859
719 922
50 744
126 923
523 587
281 602
246 633
72 196
11 943
583 683
206 277
887 918
95 899
235 838
55 981
438 779
52 191
508 935
101 431
412 623
366 369
255 967
326 350
162 360
620 745
42 826
373 928
95 819
178 329
232 656
661 786
21 203
528 837
289 489
310 901
263 679
517 618
967 997
158 195
326 814
254 719
626 991
85 998
175 444
451 765
425 758
130 236
72 980
9 468
319 360
622 720
337 349
345 491
303 685
502 980
756 850
193 698
695 733
277 529
221 394
978 979
170 215
107 149
116 638
350 617
434 688
323 782
25 813
478 679
849 979
659 699
86 708
171 243
755 871
699 975
29 264
434 953
243 411
233 934
526 902
311 582
256 590
444 966
421 921
269 644
252 302
319 689
362 561
116 859
432 557
47 90
42 586
180 832
766 805
330 764
19 697
608 993
788 953
373 573
217 709
312 993
312 870
231 1000
224 859
7 346
767 788
54 704
181 885
236 985
2 999
21 667
48 659
628 1000
446 553
506 724
121 716
169 342
169 379
603 925
379 622
145 609
14 409
201 590
251 436
252 574
240 786
624 833
250 604
48 184
156 907
628 905
74 975
353 969
242 893
307 620
268 515
116 923
281 316
531 864
103 438
135 241
29 758
73 279
361 609
326 516
230 867
143 841
303 464
546 896
356 852
222 867
119 335
497 752
2 360
105 634
768 797
178 697
121 526
456 886
133 729
596 754
248 714
369 788
685 711
419 616
483 537
7 640
136 169
110 170
496 744
626 644
322 511