1000 1000
915007820 -916467965 -281293558 718146627 542860273 882218170 221576111 -367177622 679249117 -571934823 641191625 36351257 773899545 2205688 388117941 -758376488 863496106 227217829 -947450006 53787097 -162143812 -913768486 -744829415 293741297 -284947316 933405080 804583040 76054309 188156075 -317380097 649806631 -44319752 -381331710 -778970575 -473656773 -985955085 -896752405 747919339 -353132707 635013065 -971499132 -859424729 -476119326 802400413 142780959 911998615 -955976075 -141206583 -8267203 949090272 912580514 829588985 -964678214 -979732549 -24153366 -397109178 953672531 -367053973 678945132 -5655041 315565930 181268115 950025207 934234220 402297540 -671115214 948279136 358061487 -923195875 -552337219 -154409096 -894695007 -411761948 369471578 760221758 731019011 133986546 656762036 -557671220 -874280657 458368660 -792574353 807824680 346206798 -772306902 -363812334 949097621 -966118018 269133693 480559105 28226941 -562784025 -485656428 -169231500 -776033452 916641112 159653286 -975237964 127218951 88973764 -527575183 972809856 46795109 60662870 194797786 -340466780 -355801767 -818699316 -831188392 86527014 -840463621 627180268 293952661 967361059 -174096582 521645759 -543934922 -372482609 555527741 725198771 -891923504 -563728966 -985068901 -525063580 267039534 -761102353 -755906116 -720790827 -736340317 371312836 368182937 -263915500 196639044 -732505602 796747370 -756046818 -72972382 -706538044 -574746133 95839226 379988970 -415209754 -424464154 -473542017 -595332342 401439265 -951896258 -139267264 -971043344 456147836 -561552141 989549505 892418870 -546621042 -682997723 11974757 -307723395 -438903838 291183930 -44063712 932408998 -488116781 692020789 -18435606 -220622383 341284511 225517576 706405236 634746467 650771443 -345239186 -132748211 -911921958 230296661 393709772 -507254300 -515747722 294329867 353478436 -634274714 -397005945 791926295 -792208857 -652070723 -902178394 -475206579 359904034 -209901789 85889583 -496395684 746034500 -129185067 15487535 290571641 852379327 794865153 -515627496 -69586745 353786741 -880881028 -566298949 -991452445 -161112887 -478220907 91360568 -914886762 14524793 575612846 379443105 -779480419 941338133 982437160 -987554124 -998354372 -817117211 -889732518 -473560951 542786824 -247117954 612328632 -953608860 -648567102 -664340083 -85604972 642004539 -959444404 -438223467 -873622957 -29031148 915563274 -901987633 404669903 776627181 -210584167 926448996 -279495898 -125470929 -206509859 -851366700 -893511472 14009722 -910028567 -911074312 -121028050 -908382938 -875675171 -158244215 -529427537 667111653 594637831 -917098904 566019146 946070729 -728922635 -667069474 440591620 -688367038 -105292941 419485015 282601814 -337213315 370013735 -460211931 -708069782 -988054080 -681246583 12434320 -113525009 112243558 161067621 -7036481 -873746720 103555406 -65594441 -142258418 47688820 58730388 699497367 518261284 -421641606 146651550 453678732 -855622460 -54761369 724756097 -670175582 -761653397 -963610941 224531477 657831619 171507225 887318162 -119638294 711295294 -968235268 -107692374 -969951289 44199053 778782617 -5191379 -942216974 -375737512 -26421747 161338432 558668047 831319836 -938456395 -530085213 383333555 579804889 48273181 -617498542 -114000027 45167073 327740089 -536727578 374991491 566086693 -647822166 -547960680 76434664 523685059 -808126166 956796370 87496706 -776361433 -298379652 -29938231 267837620 -667080683 964870391 325620646 -42818195 -209035004 -660524570 -631633796 -525198816 -598980965 -161719009 858134740 980823924 886554173 -906847450 -280659751 -215762402 420892639 182612672 -988254558 -160504316 534790506 -536215238 915930348 -89008083 -344341403 725243070 998488623 -120702836 -720620230 -178933255 -852865216 -387700913 -361546512 325271782 569480892 429418484 664747212 937847096 904219669 -934233752 -371355560 614870761 899106524 -632285035 708023311 -529036874 151952563 -18567698 653575798 163698005 820927987 40882656 627482768 589374687 951874573 -864342283 167134110 802879549 14954881 446513880 -523537354 14606017 -941187032 114916134 -807605849 480810212 -603149030 857141363 271173661 -846413009 775423963 899818101 768457752 527046840 -879950582 328997415 998009966 272001981 -837053930 504102116 -711783661 983874057 -602498876 915699107 425765096 -798107951 -948643176 -554584442 -995228402 -81171943 891929439 -666249404 933434074 803258759 448666730 -874171775 136585323 845517701 835485940 -739724664 999104692 463426256 -987390211 620078797 -157010552 -867340793 -198407436 -306484234 404661189 -35461366 -949865766 692877528 -199070957 -552364642 461092987 -920789508 -350472593 364966163 -475373950 -493184642 -863689428 -730928159 -159434046 -930255354 -927669400 -858250963 -951910777 61432276 987266738 736091515 321707612 838887782 52034123 334317402 311482931 895023571 466976609 -886924504 -558944311 -275845850 -69869518 -508810077 -730451970 731059526 -61174719 730641017 810270018 588352689 -51876468 -812587580 -904831953 84434104 -543515738 -211749647 6695102 -618668786 -70000610 -92699323 442763490 -230217520 -504091455 -383012545 -538813385 547942668 951304857 772669546 295482592 270797818 738261394 736538281 994951969 -479091771 -919755443 -882983649 -895515893 19069838 847657369 914754125 -540061121 -351702747 -897833455 -592376722 732731358 -588832841 195873632 -408057188 -207501626 -874126978 499243490 -912221784 -251828145 995152035 -295234329 209358470 395611055 -491413120 -165455632 -456390001 779384699 -574677885 -867335367 626853020 -53769656 -787090810 743869371 50714451 231979028 444043092 -182015072 691917908 -907659654 -227332175 -900458814 677588056 183834985 147931170 -877952780 976333359 126320545 621290710 -935888425 874492400 468959097 -378606401 -63632778 -282913495 129980479 770911590 260696504 -238118470 -951249943 393361137 -758749098 -5019599 606270327 985120274 -954305148 -309234292 281679718 -283803868 -764800032 226536416 488863958 -812742494 -243359176 -474784705 335188677 -121311955 -645934994 -685974426 -647504893 -729307067 -958965674 821454205 -107913468 -22598452 -608942938 -977932988 -399170510 651753566 -363535106 -350420452 -102368944 -122284203 644559949 -643582265 -284647577 542771154 47183443 997032141 -888516362 282383411 76084910 600347596 469640918 832725734 -874437109 -342654053 -436069869 -667855751 -28628479 -83574761 -397162817 12405847 -409604204 494923715 989807395 -18547142 369507079 -556846763 -514277224 -994028026 92732785 383353832 -263795877 -410190913 739771568 451556546 -867419759 -360528637 301105039 -903419769 921854775 -770293699 696927828 244012045 -937567964 675007071 901357992 -521121481 -992848679 -274754135 395303758 -537495144 737651712 985699554 957428571 579975459 -180331236 179452003 -976871304 305391541 37940329 -31622166 -458738275 774144452 558186921 -866450355 78217350 543283514 -226978991 -768161259 639863745 -452607864 -538454957 189307925 791404181 -623506569 -283168651 545278525 -144628050 -423500978 -876959258 -896807939 39003878 860692454 -911108385 -151051199 293184265 -238923268 -971599196 168829313 -933531727 -81142515 -862792853 -539753650 -454481711 547910420 -406204004 623735639 -56289714 366817005 855574381 -563909616 914209141 -830364224 625398309 558129674 -453870793 -805253990 -44075449 401501157 -228754968 78965293 504693218 810248910 -207825901 446101186 -488285936 -914641636 -940305730 -607368780 106704029 -873837457 311488706 96427529 -561074755 857006995 -503145699 32721241 333258987 440564588 -747945402 41349720 876654972 -981219909 210985496 354569633 576909765 757114703 549315644 -614649332 11132212 -826922972 464315961 -631658217 983325939 -890993588 814442969 -652443645 -953118872 874137239 -259812425 153585158 852816134 -948323719 -897470961 -855742269 761199629 -400616660 176978973 -53025032 -960052072 429033571 988324688 769119252 447813663 51826536 -23794762 -122760220 -338542409 -621962766 262590449 672589803 -448885738 -420577238 -959068414 -613043447 -311570825 707890907 -265487092 -264689697 434544498 474700484 888895461 139876984 378893117 991424500 284134716 -7390902 -556675807 -686369959 939584066 -664211527 742663612 780425106 -895092274 42993627 -315232006 -66370684 920233408 346225585 311666550 35340209 -128668259 862780812 614762971 -235220321 -897746282 -844291502 -674813061 -163233374 -108981198 759731437 -836016538 -367569385 -247875226 542876580 -523628532 -963740510 -611997970 -80304339 -797594117 -819897551 255484134 945069495 960527555 212908212 -159420525 -502188098 -853462472 -386670765 844037487 310720430 648669444 -432114420 26017595 115948767 332665260 128271313 271657266 657852199 965037939 -984807580 270099988 -870978598 -352376965 -977775238 524414334 123994503 911000604 912416364 -956309836 -886593513 -907481187 151690651 910992335 905562721 -782884785 -395911838 -744109025 -783830904 217417397 -900071538 526889526 -281396807 -479669605 -594576527 834551960 852995655 533694786 -41274422 363364206 351249078 -26082002 -514019454 332786832 621541034 -639278339 -290282482 -401948111 -875761383 -525349766 -505741594 -909838543 -580314600 645949057 -998846208 -822235527 863064272 -542241694 -566344552 -920766632 675175703 -613899738 458639247 -753704752 -93569343 864062720 -919152792 -388057336 250273859 -107910861 975306870 -545960711 866007137 -686196231 786826121 340064523 -325474570 -650940009 938116413 -201235953 -176289775 -715108829 -111074496 243395625 930840228 -257404352 421160098 646420852 200353954 854815546 578170573 -271953991 -906567839 -110673828 -25658743 -137182 -394094756 -92295182 611805483 856179103 799793957 439628705 -837265256 518317446 753432474 949560865 -289101678 -719525744 -848862792 -498468913 79238304 -25152566 -213577742 968163808 -929240589 -430221162 -436724191 491919510 -931283958 763629763 199251408 646886615 -655807875 292683569 -611270861 318533382 -854937260 -5365616 -921245448 756868223 -296670161 878548509 49013280 -133935416 249382308 -345037893 -331858199 960280630 -64563637 -180720990 -685671931 -985325333 794126444 100750327 835354828 864885855 670529165 -748853011 209321717 739245207 -985223248 -738910522 238648175 -788514771 553773047 627377314 530018612 698835787 -525471950 608773164 308220362 177857890 339838026 -790250005 -956077526 -558263314 -135287898 -435419373 -745466332 800148465 383859637 -431138263 667339485 30502433 669612064 355210665 -252095359 192657581
359 655
141 759
189 316
237 989
953 983
33 376
91 469
275 495
86 101
188 533
201 729
5 718
842 938
152 354
145 507
513 935
428 855
44 624
95 964
77 280
7 916
384 462
88 97
182 231
189 763
269 721
316 726
253 986
489 919
607 778
633 893
290 488
265 320
415 531
162 228
143 843
520 656
617 879
461 744
150 284
575 871
552 890
537 948
143 218
101 378
362 995
637 993
665 849
731 901
129 431
244 273
623 764
281 853
24 380
313 881
307 888
210 751
50 129
98 271
268 475
614 723
68 837
37 250
151 732
514 768
11 279
138 901
418 774
505 754
418 441
99 386
488 657
308 786
406 538
157 408
131 232
68 770
20 198
105 281
224 522
794 800
586 931
52 360
157 349
141 216
575 601
583 592
89 251
368 978
656 776
240 486
607 906
307 455
763 978
499 735
338 880
650 924
702 810
283 510
210 498
3 136
451 594
539 719
86 196
852 868
353 861
91 118
311 749
289 572
658 864
201 787
437 537
124 699
490 758
208 699
562 608
410 835
507 905
300 703
167 990
203 906
348 871
181 672
448 596
311 821
253 960
790 864
339 396
237 840
97 399
56 935
121 961
465 467
25 116
367 521
282 426
504 921
592 773
36 221
187 857
440 883
746 816
563 581
85 420
533 799
85 170
130 940
558 756
582 949
469 871
300 504
220 247
7 19
394 812
350 591
474 602
769 789
571 721
655 683
481 492
187 662
126 918
143 475
443 881
103 408
60 912
510 606
279 964
442 880
358 471
311 792
296 932
80 866
5 762
848 873
59 595
509 864
4 537
338 769
97 446
709 872
477 508
218 787
98 793
150 580
371 920
215 460
655 891
432 659
304 653
247 506
363 367
251 462
722 799
167 371
242 247
755 876
71 445
863 893
472 542
364 461
195 823
27 201
459 714
211 718
68 762
316 476
777 786
78 507
449 927
525 674
690 901
112 279
345 523
239 326
347 689
51 893
78 864
93 929
303 536
649 998
313 722
125 508
202 441
14 367
39 650
243 692
874 939
155 636
396 481
742 874
521 924
736 986
1 78
16 888
13 732
454 889
13 677
117 313
326 566
568 835
78 365
611 655
765 951
290 698
515 597
470 792
439 777
557 791
573 855
31 938
585 919
614 743
55 931
730 848
733 917
415 449
377 994
103 296
142 745
90 993
259 784
697 911
468 561
767 840
40 870
704 976
788 799
70 589
205 671
917 937
587 684
385 932
60 840
227 553
571 584
842 995
355 905
267 891
724 730
33 115
88 599
91 386
31 238
443 455
53 723
379 639
116 406
466 922
500 955
370 538
71 364
425 731
269 621
43 344
350 427
459 948
514 549
104 685
491 931
546 984
214 924
971 974
248 391
345 788
158 747
234 817
521 965
141 593
635 937
287 485
413 943
586 927
623 843
30 125
113 927
460 678
202 786
593 649
33 436
779 937
523 593
466 948
839 892
775 958
442 879
291 413
736 999
217 930
598 973
85 407
524 866
115 726
651 763
670 683
198 958
143 814
113 480
318 960
4 917
445 882
711 857
173 798
207 741
80 179
486 691
566 616
351 730
291 354
312 492
41 388
270 553
535 749
494 665
419 669
215 763
473 550
71 74
278 622
701 815
808 857
186 423
422 889
65 152
242 995
376 981
388 645
274 534
198 746
120 516
218 882
730 768
706 800
193 327
359 429
237 380
215 565
11 637
163 805
53 398
428 509
248 379
425 912
170 522
109 641
37 327
766 874
446 931
917 990
609 698
349 988
286 915
296 905
709 903
458 955
107 319
383 485
566 807
439 748
208 328
79 364
304 886
481 683
234 749
673 843
373 798
83 830
287 734
190 379
795 836
144 253
506 878
72 89
36 836
363 510
43 941
78 281
596 910
830 963
11 635
672 808
359 853
646 891
269 939
85 187
456 682
314 337
425 560
595 737
260 598
310 654
538 739
134 934
249 649
11 315
338 883
242 818
60 190
239 480
425 680
136 564
106 900
17 449
185 676
287 612
134 273
672 941
11 226
11 157
474 823
21 709
160 839
302 701
250 540
181 930
96 316
417 421
348 865
23 790
401 401
310 534
602 673
35 557
65 179
5 46
66 887
398 713
14 256
99 506
631 905
220 435
726 851
73 992
67 781
448 819
109 533
557 704
261 710
240 592
637 677
244 916
54 956
310 313
321 411
577 815
41 601
119 796
140 803
543 869
272 990
157 687
98 742
159 713
354 656
31 399
644 994
698 946
258 950
359 622
21 525
199 413
125 346
531 927
74 485
109 147
185 415
265 865
329 926
280 375
125 985
310 980
119 607
29 420
216 387
41 236
263 591
387 649
531 937
665 773
811 956
371 881
145 995
587 921
826 961
162 552
213 438
141 556
522 819
34 327
260 719
523 622
270 310
246 261
800 926
18 756
88 251
435 478
64 747
572 707
258 376
165 733
226 470
72 288
398 747
6 673
117 294
426 880
141 915
23 715
66 392
153 822
642 651
741 939
66 645
664 793
397 902
723 958
29 974
10 72
35 427
429 895
309 328
243 320
449 694
309 866
85 482
79 370
132 309
549 819
482 953
207 341
230 298
555 929
291 327
105 978
325 407
4 351
22 715
515 598
258 715
151 380
739 749
222 229
399 409
362 770
111 233
814 920
760 848
369 438
138 346
814 894
104 244
170 818
265 767
684 979
25 415
130 763
516 710
337 924
458 461
637 693
556 920
506 680
226 404
469 893
363 924
59 379
606 876
223 549
232 994
18 553
682 999
133 514
469 744
204 437
74 926
198 896
753 981
736 877
331 345
606 629
59 687
17 984
532 914
239 907
116 791
114 277
409 825
920 979
229 415
123 506
370 840
173 703
474 931
804 908
276 536
409 686
393 574
702 839
276 292
98 391
435 726
611 856
134 834
362 530
4 249
219 440
373 922
198 612
520 852
2 479
407 762
165 333
218 506
523 782
862 972
296 524
380 697
182 906
213 787
813 895
114 790
514 605
35 568
238 711
87 712
717 846
233 826
530 683
404 450
464 663
340 376
424 958
215 719
283 606
1 500
448 790
52 965
655 999
366 619
58 237
305 429
254 255
537 784
338 937
539 752
1 914
310 443
338 513
295 877
796 877
146 595
19 111
646 673
109 616
390 697
673 819
279 353
72 889
360 414
579 953
464 931
218 906
240 555
419 468
201 566
347 697
160 715
157 457
739 917
129 772
797 966
318 947
370 427
559 841
82 137
545 793
10 67
658 802
572 917
469 478
174 489
648 815
623 888
156 978
280 892
458 857
76 756
174 502
478 732
559 694
220 486
455 638
256 848
648 764
125 180
584 668
298 399
537 668
373 823
264 514
102 324
120 529
79 646
31 556
724 729
114 949
562 920
409 586
176 233
355 524
107 357
6 374
41 857
230 542
56 864
845 965
731 965
494 809
610 876
690 717
182 951
512 638
102 576
272 629
147 160
335 869
606 708
814 874
416 749
43 612
240 823
553 928
204 773
165 713
648 781
599 854
844 963
416 462
86 419
396 930
584 730
189 798
24 437
3 537
397 439
148 613
428 636
191 517
200 581
200 355
362 561
676 798
611 756
174 443
48 838
455 632
253 567
172 355
174 276
66 892
391 923
678 910
170 546
101 370
126 807
569 839
718 719
474 866
308 680
728 999
454 497
415 711
706 882
333 770
13 408
330 398
403 427
591 925
324 691
294 449
214 850
568 640
505 931
394 962
165 392
41 661
751 845
76 902
197 633
40 586
209 983
721 963
311 761
84 887
354 532
203 885
745 876
27 122
380 515
544 989
29 259
103 557
780 984
357 764
180 942
388 803
277 875
389 702
185 589
538 825
61 472
92 217
566 936
243 315
80 583
211 338
119 612
743 793
102 501
281 506
660 794
20 70
73 534
70 811
13 635
485 960
51 695
630 701
295 616
48 296
506 878
737 841
881 976
77 583
381 440
175 709
80 451
596 984
153 406
165 405
364 392
1 86
415 701
382 715
11 348
225 429
166 868
417 844
398 999
272 779
790 981
240 305
60 252
564 575
658 979
49 729
81 343
109 487
553 782
481 490
271 915
57 783
436 473
185 978
249 471
612 963
581 619
641 851
425 871
204 880
284 755
97 280
365 766
205 498
47 319
233 330
317 386
104 367
696 858
288 680
603 945
291 525
221 493
443 517
73 917
322 671
708 954
120 424
676 719
273 389
602 722
38 622
340 987
196 493
36 781
332 875
383 517
208 955
9 725
277 398
71 149
208 300
24 419
95 632
94 256
168 483
210 456
548 557
50 796
183 744
830 970
212 514
487 721
495 518
797 915
772 945
71 338
361 505
488 841
286 455
290 743
304 453
10 745
852 892
59 947
74 240
587 916
402 803
308 320
249 456
235 372
753 924
257 794
284 986
91 744
271 838
76 732
476 494
85 345
495 720
291 793
206 734
732 888
391 960
207 560
793 846
283 598
76 716
206 352
61 301
683 794
491 525
758 984
194 352
71 328
688 970
216 773
527 947
660 838