1000 2000
340 237 43690066
217 141 453160975
744 202 639037814
605 926 404985542
364 767 11240650
116 495 800978683
666 916 795700314
67 954 158962570
314 927 821562538
959 196 325114995
884 462 755167248
175 802 438729355
857 102 891684566
68 865 593380792
682 608 380623094
287 35 875208643
355 242 609011072
112 657 903744064
359 542 286164651
449 232 410025965
280 870 980084335
217 983 396348916
910 72 196230528
45 828 430847049
816 627 200045106
676 233 592971412
261 683 172801973
148 276 806396118
223 51 51914201
616 334 87559953
33 44 854595660
979 860 44790753
763 157 405346652
409 609 638142121
774 300 800447349
944 892 325573557
737 687 899774408
862 872 123232156
508 33 872261076
857 252 89576773
324 70 337061630
742 474 616786766
168 601 981690253
477 497 551750586
421 17 129633716
81 768 54734295
242 132 473143040
155 685 681935065
200 805 269655918
642 286 116673532
190 596 678634382
531 787 760588593
272 697 510291038
902 751 921715812
947 558 783253104
989 179 43715962
386 533 906109571
519 322 707053205
551 933 800791396
173 601 163422689
465 57 301214384
595 653 266935366
24 202 70478563
624 874 323690312
216 285 721627062
70 672 752310959
826 646 361062973
153 706 345107113
487 429 239345816
497 433 230391924
598 664 854263326
458 257 938917417
692 266 840987079
115 335 488781570
122 185 34492832
195 305 29355762
625 821 469449390
892 417 339191129
23 815 723475758
144 508 918294968
222 477 764306957
38 902 508423742
52 579 966773697
24 916 430582272
279 204 547093001
241 607 949133
787 349 531883708
93 427 812762100
251 538 613116396
66 545 54510387
615 271 647993143
696 523 460838379
604 586 474774129
82 139 558972643
334 818 1438213
899 867 796706955
517 308 174327714
954 663 337614525
678 856 43228277
612 456 540026252
934 777 261501245
210 362 403313343
20 963 224181721
937 709 582935528
283 160 214720423
905 37 283020506
667 729 410708136
787 493 882634176
362 251 20923709
527 98 250510526
551 930 937428618
743 350 60056920
107 203 734546602
233 522 14763389
244 36 658342941
141 200 244541512
662 884 849121337
712 187 550909988
968 597 529000999
678 662 232311418
678 662 716306942
263 496 184028986
299 493 39648256
57 64 574603555
638 965 666813492
645 381 841684546
397 344 499042820
466 306 17478860
900 499 913963224
964 221 659088346
751 985 49101272
927 690 598462908
566 304 384906508
388 473 497320246
572 118 876829236
532 359 123884194
875 72 323874360
915 52 527185184
410 566 697905782
455 451 505152241
426 601 808929286
366 143 592536825
318 799 723976295
800 506 530162160
665 663 281614325
402 509 723186053
277 396 530589576
381 434 225634901
113 37 40597198
823 476 896104701
282 580 230120531
707 510 967600826
50 257 447710136
754 334 123507330
641 555 82364705
783 633 721292379
184 65 997737058
924 642 133077120
949 699 204291691
708 973 998490705
468 969 582301734
722 665 516049905
415 510 375550447
204 281 303877737
78 179 234714300
741 163 21277637
165 424 845870698
32 104 633794145
644 14 826700193
217 141 668022595
770 238 529708958
29 837 846061969
231 918 109972424
262 376 11843870
258 283 187484815
19 470 341344237
635 898 230906918
546 501 599797576
798 714 534974162
835 66 245461651
980 873 228041826
920 739 104115557
408 483 845866756
690 157 114559562
247 174 859092831
458 65 695225207
29 869 533995840
488 910 291922069
92 237 920731431
456 120 401861077
536 365 438530652
629 857 601290708
291 727 333161925
527 87 607846362
352 36 596368848
950 399 576971337
819 1000 323215317
417 46 808184762
582 541 965052238
594 12 147116207
801 401 806387165
499 944 725914647
272 898 251233892
280 40 645867551
67 456 477063700
541 796 243136281
776 906 820345988
713 782 682582225
40 923 798633611
752 128 716488348
640 404 584936665
792 828 669913234
180 853 614984266
674 628 363909122
652 388 326083273
7 418 489300613
678 507 181452419
71 185 402906396
608 744 984485790
244 805 527532104
26 104 108565818
621 235 678396376
744 682 147101619
764 953 170610079
51 214 877032000
92 155 717428637
360 972 563277457
265 33 504590614
929 6 734596278
143 190 359494445
590 567 751607458
364 79 120218707
78 863 230673831
666 729 682384048
788 926 668400719
365 904 765102051
922 678 886647279
114 419 295032727
263 998 186874835
558 400 527560591
156 44 839918666
412 527 495000184
535 328 183971914
789 851 950141568
141 603 902350830
135 571 943551188
206 366 226800400
672 75 166007809
500 451 608827954
111 369 307118062
269 183 129309473
241 170 435397765
141 803 347621315
606 98 708651597
352 141 551828250
721 175 259115870
319 146 944150386
675 970 736781610
268 918 528758342
917 347 469735591
600 633 886522367
685 656 521925594
264 389 204910571
912 446 579189168
178 675 587084568
893 120 605258032
875 185 499819561
450 318 338488619
799 450 620067013
422 268 241189702
95 591 696884205
375 947 967900592
98 942 762400457
314 690 801841621
256 492 374934584
124 108 88609004
258 96 400525971
337 660 810034570
4 285 22012655
81 145 809453816
279 230 532711454
282 955 394118513
976 460 504376954
439 540 323931772
255 806 929540758
845 485 48717057
906 799 735046465
832 813 643532423
533 477 388372917
160 501 664784322
621 159 400177919
997 870 122712712
561 933 658915187
363 89 498330125
966 883 733902992
118 392 777649978
360 164 793995273
445 174 569935416
747 864 183197819
593 755 958011258
567 31 249103052
855 500 199601984
768 152 530302966
114 397 639897792
700 832 23955968
846 828 569756
513 638 259530992
434 913 527517201
329 448 325474473
960 829 1621926
553 655 341797528
656 279 180044012
828 105 466296404
913 998 584680553
426 580 19025338
413 110 306429950
210 538 702103868
436 856 507104851
887 291 728948987
885 609 449259635
90 730 595284815
990 205 400673637
900 892 158411610
686 90 26392090
415 973 623316108
767 270 483907339
158 689 340471020
956 415 543687634
895 596 882032543
829 378 910910847
441 103 508484500
584 834 975064441
123 892 33124064
364 767 496458246
693 87 443067517
908 232 173822218
411 760 116106075
870 280 252779
409 885 906431214
484 715 827369680
824 224 753505882
952 866 659671517
414 957 471937224
292 793 986636331
332 154 963310258
277 142 690986693
854 874 644018785
829 321 25266100
740 393 373229216
892 339 811088667
727 888 873633080
387 836 810691201
710 188 690699455
623 937 916899744
705 228 598364242
462 928 81101419
925 894 712585112
363 2 803407140
534 949 988019288
788 260 391395805
239 250 663469315
783 812 910517355
183 541 117299149
681 616 777707228
595 653 538983041
282 460 717105075
357 13 724039475
394 93 328381397
584 308 760903768
397 778 889984296
150 25 266725134
987 176 390437461
308 39 119687806
939 548 720260836
286 860 102879311
912 964 747347401
101 677 524940667
937 350 427535227
354 72 294697632
778 728 768743116
431 439 91547771
776 906 604270247
944 757 835553351
897 448 844746438
963 668 468250357
980 91 393660577
609 299 345017140
480 804 260421450
875 191 477400062
68 865 370005117
886 292 306303903
419 467 662466542
261 859 271688930
565 300 376007730
747 730 452808227
113 543 850898814
504 240 541195096
323 77 886188673
369 945 424945470
505 342 186665206
319 435 281232627
57 374 175994575
306 107 606676423
62 995 48706743
451 770 962075685
513 965 276608771
49 131 604608834
141 241 571610595
549 882 337902023
344 11 710146510
730 410 464197421
664 368 733707700
626 793 312014388
989 68 599488006
677 986 150841787
863 544 351841702
267 489 534164098
640 519 679193178
879 286 207877249
883 542 191599084
627 649 579700397
813 981 34899570
394 205 396281848
43 301 461573379
801 227 119392719
202 608 186469715
888 439 142539534
763 992 745126800
577 426 565759095
55 340 697975033
835 945 185620661
923 127 826789215
910 692 817040966
974 819 9328519
891 859 936265413
250 371 181728508
974 706 19067124
986 443 490846182
269 901 180064661
94 183 837143261
72 488 177396400
536 307 58286219
894 100 896260170
303 217 155714967
348 184 890251395
349 639 757761461
219 588 230666461
724 943 401853346
740 885 720316218
812 783 476320724
468 459 244338926
938 991 717600203
125 885 7852366
501 404 683779046
134 225 357947903
429 364 322548734
578 60 152919508
104 566 86951275
687 516 948125353
259 404 660908250
161 285 546130888
359 378 326885216
593 721 916732577
289 295 498973260
527 343 16804615
670 675 868857191
88 73 548311786
318 332 8903212
371 530 443887390
993 355 976756292
864 908 126528498
245 695 55271625
121 581 169324553
202 666 205559532
654 660 710206333
861 744 9865505
851 54 362386474
869 581 507549756
694 229 886781080
574 361 609204981
719 499 146298118
995 351 984209728
917 704 489260719
961 778 139220758
768 345 606229555
297 952 341706534
455 218 148592807
412 600 496652353
423 335 548695751
170 425 687215624
65 871 350907514
15 511 422138401
246 873 385308147
335 58 709886524
825 722 59239993
164 972 61072835
283 416 788809574
224 561 697394905
973 956 23221600
416 929 232896116
126 337 205085592
232 320 446271840
197 311 205008279
763 193 715212765
945 481 923130542
418 453 591387200
975 365 434315611
708 472 445939882
280 129 247539655
379 674 698667
266 68 226998650
521 670 512131812
600 412 914742728
79 734 289065897
575 636 206545668
715 382 484754712
326 126 498478139
329 374 57024040
320 686 880565626
512 171 542382301
743 23 947337641
53 764 820151021
808 940 304134611
393 950 875700716
370 33 813481680
382 243 161427533
280 129 138858721
548 247 269259251
792 539 412984971
33 144 54579460
399 962 952419377
180 939 748550406
432 429 857744899
278 713 12487811
844 79 628112278
912 903 483462425
591 955 427857705
83 608 19807192
120 274 408551816
857 535 542923215
63 539 925919231
858 362 1214751
763 936 18523037
490 667 682070459
839 558 128800571
374 330 891905217
118 440 140328930
272 697 934062657
956 634 653922810
102 917 784180441
13 250 358912287
943 840 117078614
397 306 837638187
31 102 589599085
867 514 886827479
509 733 742004051
546 447 21348569
564 987 199356490
152 961 679035213
200 895 567857541
10 199 775331697
433 183 264857525
676 935 305922523
743 372 791416303
672 195 290287702
459 969 382043265
566 886 991695027
140 17 14523577
734 390 448169141
353 138 497435328
681 968 976051991
221 912 30176497
312 839 271915839
249 876 546714533
755 297 21240753
591 246 424343545
632 151 747949822
681 106 911202786
981 886 215822594
454 957 838439772
360 978 273748396
868 9 222136912
97 742 758807801
653 610 572669133
391 363 702456757
347 158 128497498
218 705 375023410
38 216 591135361
414 454 353084707
143 142 844591790
809 980 622037320
458 871 491647899
736 813 916476672
581 272 763749444
190 716 555982191
494 33 333655237
825 906 655883144
819 153 738771605
467 466 35918436
581 327 863615504
246 577 766150643
494 421 330696921
136 965 323445838
967 791 462345770
8 729 766123463
42 157 314071922
210 538 937192753
797 835 71265132
631 18 967808630
784 408 265742350
46 731 40772863
643 362 775544190
315 38 134552164
662 856 9871743
166 943 748732137
597 639 262285747
162 48 456691270
569 257 511603959
864 862 662491622
577 478 136304303
477 181 440137687
533 149 896341376
159 254 170209524
442 258 138737806
642 263 142807062
111 177 297638482
299 125 587054535
699 464 547141574
582 988 288659073
576 358 51722425
389 893 292829520
563 297 882237245
994 960 725430736
436 511 270588021
935 589 562731083
601 282 232184502
172 703 679900211
493 256 774201963
353 816 650221131
464 676 540783499
754 770 172935591
330 357 304970362
617 278 267256020
845 299 117329934
906 332 510207734
524 237 128550601
659 531 721893360
584 639 326372717
456 388 485866159
478 976 492841613
157 745 827733466
81 467 2131846
622 543 132711565
955 478 752234757
543 909 583461067
839 214 393712069
836 133 268781967
732 412 827241990
674 220 519515209
428 62 979917926
166 525 794159170
935 969 341429148
45 707 593299246
76 785 641128156
622 543 709112658
69 117 117524490
808 395 329468896
888 291 114483818
314 690 160906691
900 146 894401923
971 85 603744051
188 457 641251538
840 166 543963545
978 418 900410137
832 240 581271338
781 375 733119636
239 245 205774684
669 756 148381623
471 533 845265836
930 919 619199137
898 560 401939146
747 320 414084293
613 87 596024785
952 87 215451904
453 723 257502047
939 458 423998354
972 418 275134075
589 625 349162084
133 283 130706571
91 178 338148385
469 917 834218379
568 112 370432222
878 422 74866835
275 619 384694577
116 69 969612772
995 679 550354707
610 897 993367872
252 208 861315541
947 414 859855313
156 302 466877386
480 430 307516177
792 707 639130737
684 349 11950767
112 124 780397709
816 4 176005670
209 143 192658897
687 901 26780544
654 89 583144830
803 36 880557385
253 623 133192666
903 795 114692620
678 833 845162546
199 673 621557855
569 548 510877520
202 925 112318985
314 333 47635987
348 287 290838844
774 744 842733906
420 630 821075613
344 114 493485123
838 139 926836305
161 486 360191842
525 808 170115138
52 15 849478679
670 673 53900542
609 377 826576279
698 745 645125346
483 31 803083873
446 21 233509480
234 990 157566034
489 441 84730096
878 231 577951382
322 537 240652014
358 198 347517975
149 229 358456016
419 762 717755004
472 26 598260693
855 705 954927063
233 625 805130393
866 721 835933809
40 735 310066011
650 264 811573535
925 325 569563133
586 747 189851668
151 174 893293255
700 586 900905845
473 890 663951944
336 989 385810246
393 787 804248565
751 932 528153962
100 682 813709619
424 88 558299918
961 778 49295017
93 585 501090861
136 554 251233751
821 769 170650762
529 881 499844840
762 467 560757472
105 792 367532708
404 322 294248304
415 162 362845633
219 43 623998615
376 525 474538357
329 525 348051558
542 378 842603205
463 979 48833005
847 844 445011719
185 71 609217738
569 648 832009335
907 405 390800133
392 872 410099649
828 576 254205351
366 209 136284127
507 884 357879266
471 477 794050741
240 813 644294204
34 167 410622659
267 489 493492116
554 444 699125092
238 798 352825349
810 307 426914168
728 203 727807557
948 160 939653164
883 681 657002701
573 123 40148487
913 642 163183774
772 611 846380017
623 121 51729399
263 313 972867820
573 892 752479204
163 773 186391612
149 694 593673928
289 278 917558720
451 321 629895178
813 504 762443674
955 976 393407835
143 122 835053340
891 924 791968438
158 523 125475276
462 436 866246378
614 402 597441615
265 637 513565143
3 837 707577139
808 12 68507089
196 220 573514559
457 159 764602225
852 631 130079400
518 642 78915901
683 380 286670438
293 640 498405106
422 878 951655027
255 411 357787839
453 660 477424711
345 152 311669537
330 395 165312138
686 736 667547948
313 518 895441634
795 755 504415197
331 779 236889973
979 998 8389112
566 304 934729794
809 383 410124395
98 812 45660018
538 698 181797921
726 242 422987770
655 444 196286549
160 258 869275340
281 115 673015659
866 498 921584106
255 937 923614191
856 915 26307171
288 97 824558145
445 959 396021275
500 958 883940312
227 401 648551628
18 646 800250490
940 628 654900578
646 679 486500502
127 325 421967473
440 753 858234540
90 813 874262942
232 449 242568307
119 999 213716120
926 128 671414768
650 204 169823441
786 671 744101573
65 564 417580322
683 69 428425456
58 230 188139362
515 2 34808886
962 517 318230827
496 860 187911591
157 333 771245211
440 872 938068899
789 109 327133067
914 291 987984431
31 800 831290051
302 370 118084842
556 43 304662027
432 782 354461263
693 613 73007479
311 10 151212030
915 579 985388695
537 512 113749260
446 964 973147912
386 222 596210817
475 438 697093621
295 487 356865000
820 763 558751014
656 55 510733616
962 994 791626398
228 855 695146264
465 840 866871095
954 652 621813409
915 507 479994414
688 234 931803507
312 558 696949921
517 359 148303846
460 95 466468782
119 982 541846079
622 641 305008027
300 407 345207556
211 921 295421044
592 897 964116164
35 257 852096273
585 996 220099457
679 843 874171847
73 978 117097119
546 147 63867440
865 512 657917310
294 570 282270061
82 459 200987547
62 653 641515214
639 137 861093677
5 183 337233613
44 367 495047173
327 823 363119148
323 55 199941262
126 723 196509646
747 730 919288021
288 132 128377955
311 980 766882537
982 999 331936893
988 477 751790491
659 787 155615644
425 94 797771436
169 809 496717828
352 725 680531604
476 743 241098168
416 442 760094315
123 944 343120986
14 587 433736943
130 554 163521338
416 86 933021888
528 288 939747035
711 822 72183246
233 911 78479784
984 104 866623212
485 579 588711526
47 965 294184372
215 686 817597400
975 819 192367172
756 791 334072389
493 775 644985280
685 423 807443966
99 673 881528079
827 656 826128718
396 209 728758741
180 672 852588098
430 664 601551654
560 29 756852778
616 818 318632345
882 216 189530882
60 807 829168
124 543 697495857
173 480 227906454
985 772 94852027
977 716 40788667
775 299 309795000
196 324 758326423
647 819 860330989
426 460 593126119
865 971 344095764
67 701 111084359
991 313 501219083
211 136 53515624
201 273 846125614
631 766 717048098
681 308 935278843
356 248 720942378
496 571 816738027
972 88 725657268
643 936 666069401
206 303 863063915
942 563 571905697
125 787 874227844
474 833 376634032
552 568 488217769
611 22 156229729
423 323 754322149
651 40 847716283
850 43 241426257
706 1000 638646516
272 74 709677394
886 984 958720311
984 981 21405308
47 921 638197681
236 788 250264627
299 787 818319491
230 264 169642240
944 561 900131167
100 202 246059818
235 621 60891425
299 294 101171004
429 289 531931951
363 718 196865260
89 20 880269897
526 558 763252696
440 794 197439463
214 312 597734640
16 669 607242462
513 638 969361819
833 877 692832342
865 85 350226931
422 268 15053066
81 768 887044668
340 524 276608569
570 409 268425253
792 358 451541259
60 448 111787463
197 980 476945885
323 204 328594166
443 878 778365922
594 12 845404032
935 949 201312530
395 840 156745240
341 420 870452140
608 941 190032601
537 293 182861859
105 792 523242942
449 862 34934632
903 942 72439394
432 627 666576183
3 560 870908270
67 776 692704111
658 458 210658262
613 633 959563703
188 243 662079593
716 373 153303601
558 223 503581581
733 614 825279531
501 811 153930385
629 158 583782222
807 374 174457098
521 675 102396010
503 466 541706517
975 133 255916976
24 213 919165581
393 787 982732631
317 168 413442804
469 30 171304349
953 765 856007599
880 117 770847251
262 376 678116074
916 941 555131682
635 823 255841193
665 825 369281832
514 336 172388123
504 292 420171795
475 21 277793671
875 277 640162988
221 175 970067458
909 187 278286964
917 696 444870882
343 527 628606595
38 806 231743302
539 207 837727014
837 28 42409776
964 755 577582491
498 964 186153887
694 229 230489018
510 846 522845837
247 648 414895257
721 593 381441683
334 321 402528037
599 240 818964224
530 239 674197423
290 629 309305508
545 92 204683202
612 473 402193149
828 707 125410160
413 401 635521930
167 605 60268664
863 122 780276052
24 651 795139483
730 215 828494554
511 854 327464750
107 419 352366230
11 152 819781871
839 717 465234656
1000 647 463701643
606 98 311634688
950 584 381253060
852 437 672444191
383 521 559792339
198 792 511558942
939 853 565906202
63 162 97597388
807 852 470502324
234 669 202575763
848 889 389751069
378 542 817326677
69 891 856656263
291 189 403364849
688 440 936057065
273 101 458736674
146 945 264140561
667 325 403408586
888 431 260035451
506 347 641593413
510 358 504492797
464 233 26355347
251 745 401383383
117 261 143226438
637 144 489052439
195 680 546344748
940 840 341054949
205 761 377348058
218 455 117204111
213 894 264233051
563 755 518812086
883 39 453744196
826 595 59315270
389 893 628983848
244 131 704507186
456 473 297430147
996 234 32788626
628 262 579215417
982 745 210442919
804 173 882747957
886 626 448757587
639 950 487953508
449 586 525660706
827 115 331399028
566 410 425570634
551 824 386447419
633 952 397652723
755 175 608525225
994 960 207465424
147 96 954645539
167 752 595570934
203 81 956684187
119 643 589307906
33 265 387669777
724 60 610934677
544 71 361139283
4 161 379248020
392 449 895207001
598 108 534513325
209 185 976537712
24 703 576724086
121 937 879814685
814 355 748625727
981 292 861442394
928 470 267411283
149 888 692808805
991 879 195443291
513 553 601462968
438 830 831692188
695 445 739438485
342 406 82872065
90 320 843106293
602 424 245845130
667 8 79981009
223 947 966557964
145 561 599397330
552 641 603169823
783 693 292840186
405 602 649489601
968 994 244387506
977 692 727609531
876 614 928162415
128 284 254654214
470 742 31591426
567 535 445881927
671 906 201206178
740 659 935712801
772 22 876729029
551 919 996062249
327 461 663331748
801 331 826407935
664 44 756181721
384 482 305515040
43 762 440350596
907 7 58190768
680 520 146170805
272 869 158877011
485 775 963693860
278 364 906610953
794 604 413889956
762 301 582693107
407 385 752951823
586 872 511714227
395 357 951250072
158 857 835250675
254 614 871503284
267 577 915321273
290 615 648148255
858 502 994365161
89 1000 488933474
258 147 768039319
331 248 622166512
390 617 320488467
535 298 292271968
443 101 394895757
194 413 59961116
119 698 87935071
824 561 739203356
947 400 95073190
7 360 189721990
185 277 299124053
339 435 472184564
111 481 328771711
602 458 226704427
197 10 357187524
603 241 936744169
63 510 342355977
310 324 614735857
868 147 467247958
497 94 53545337
876 475 972065803
351 646 394342560
131 346 630158198
942 721 555618495
531 787 50803228
288 951 618324087
708 886 500480095
799 671 792653894
126 654 773085936
469 773 700951528
630 453 762986495
759 749 175405648
305 180 496886181
481 111 795685066
13 940 226550785
292 813 909021547
189 82 890300526
554 390 581575886
427 714 949134817
39 597 954404500
181 471 328017845
27 5 904634538
209 78 876706240
176 348 809707389
165 164 733241778
859 116 153082605
424 418 857915064
953 712 786099723
569 648 652756323
718 212 118456655
812 563 539482072
179 875 303313227
207 45 816001789
690 982 570997789
915 511 84717117
188 159 137660104
116 645 175263395
717 781 254953691
897 403 809867848
649 353 248233499
918 997 441408256
368 140 937701931
300 703 101109293
34 236 684120201
620 526 312570011
727 838 398342536
535 857 955189403
248 956 218826179
142 396 438238294
866 903 644672899
818 754 511091255
453 326 899178278
469 80 94791067
400 375 379299192
37 53 174818820
333 982 934806718
22 806 370697396
587 400 273232438
182 831 430124612
871 50 327008221
477 888 786833787
208 917 878093871
565 172 427607064
20 904 881294560
728 556 7160414
125 740 17834102
650 389 624814403
957 732 281198128
660 515 470518489
509 338 221643557
489 426 33354184
516 582 146221480
452 255 203663985
985 315 804674506
983 607 650578488
151 310 490848681
479 56 967611745
6 619 508172541
830 338 322977189
547 644 887292515
746 165 244227016
597 532 981900566
950 532 518319590
535 252 509910665
952 593 938390669
309 574 50049062
769 699 249403301
774 172 964978126
268 590 858820806
129 651 836540461
4 562 782674730
56 498 336838261
749 759 713396988
971 354 814805268
799 559 731821164
59 540 376504561
747 700 885844158
909 187 838289772
871 65 72040005
807 403 780493770
6 416 63607866
798 702 177611021
495 522 843422079
476 581 570008548
583 988 736226084
485 570 781586726
967 16 371944229
344 728 883474355
22 934 852992989
919 573 308699567
663 786 473976207
312 414 390735603
75 632 983483313
655 513 904397031
538 858 311281694
369 835 161486938
859 880 149628107
146 719 278735372
410 984 952999454
698 690 761103778
105 905 792599871
137 684 412988060
461 635 457700325
941 923 923594743
345 824 563165904
822 269 885897430
640 537 6729387
142 396 650370626
17 976 646547789
13 12 715531926
382 221 942643047
93 500 801195009
901 425 170022227
473 388 293866655
196 75 46226132
498 557 624351957
797 835 502669781
167 820 651902989
421 804 269950544
429 432 510216657
811 275 120015793
235 159 280864696
999 605 334186883
458 184 816561782
997 443 519667136
304 32 256870389
247 569 820299667
63 707 963185619
695 1 144574935
161 315 201093453
777 751 773948404
329 465 833689513
618 390 491926646
602 176 582683890
704 80 794051723
16 93 389029279
870 280 955066872
383 169 591330125
366 895 385658964
842 869 724040376
133 975 210057233
48 956 982776627
891 380 432885919
900 499 787201617
665 388 34926651
177 369 316449346
598 367 749734707
833 877 256714341
565 300 321962482
168 804 754971796
316 584 992128550
814 991 751491328
193 192 425626882
752 505 308399652
681 399 162791174
952 633 575171873
972 723 262965110
527 783 493754469
222 59 354439127
11 114 842042966
547 167 52843492
596 803 92407437
122 190 538411522
845 485 585863575
932 985 771699485
946 664 208885014
834 920 108020598
15 624 381380097
146 545 632843620
674 395 444044521
975 536 560835703
585 990 87599892
325 8 339687093
977 209 994992200
440 148 129497333
331 626 2971174
654 647 652379408
459 76 292119531
691 369 173179641
132 528 845089270
111 481 95010938
723 341 335080561
211 921 824113583
350 74 987653712
771 356 809337769
849 749 589124658
103 199 191500102
105 905 662485203
403 64 315685768
406 236 805407987
65 35 255038231
127 8 21638804
730 700 703060342
269 607 682811444
229 914 73590274
506 535 142711938
977 277 158357007
776 722 805356711
181 583 483952016
736 90 60607978
350 837 647960527
343 412 40771580
330 724 242254578
331 413 901081804
138 816 274338450
910 71 198600975
728 114 31041576
852 826 363309692
760 697 181709989
532 308 957030532
970 169 580197582
933 789 77005967
599 215 904949870
545 146 746024535
916 24 807463678
42 192 809811196
145 345 390144791
77 279 507855912
556 503 655131276
920 308 400705443
335 77 494318844
927 34 472860759
624 874 91390994
721 557 194680635
518 726 760553802
543 113 655384443
346 983 195494262
696 629 717760204
571 463 386180920
825 67 855776472
128 236 120039827
14 505 300573730
761 967 598748460
934 411 111678047
619 948 256137953
86 387 983703095
272 74 121035044
85 899 610484252
636 93 35181570
442 836 567173295
215 599 114353857
731 719 665873903
170 711 966361276
365 810 729536979
10 790 189518556
365 153 739832308
116 998 175339372
719 417 622052405
402 254 957855113
124 909 608821330
146 339 501472813
932 816 494690173
675 980 511647105
176 746 252667982
367 156 890136670
999 690 285151943
380 116 304663302
109 145 615564422
928 511 326097625
30 750 741756517
853 871 415815800
520 548 370401542
456 776 609830216
512 989 66228314
153 975 546240288
165 424 652479363
246 441 20124196
279 827 740265301
51 693 831414912
112 494 426164398
231 878 406618010
17 804 83785103
12 379 397714661
414 527 220682563
494 598 876283700
771 32 860161281
45 707 255291581
651 40 765147986
827 237 602325726
827 650 626536528
819 25 881078
909 552 450663147
861 774 488204691
457 509 357527409
82 468 332203740
421 817 965018312
602 348 97425528
959 310 657293480
817 430 365634959
846 792 482774783
415 634 908415823
706 904 799744137
9 86 262886878
739 517 857436088
904 718 476580034
765 712 734880644
430 841 811093918
532 639 773800779
946 17 766267188
805 49 183194583
951 97 270855630
872 780 595434306
179 692 821320493
526 342 741935229
547 333 518307705
562 315 741620815
555 622 218461045
3 411 635634981
304 331 922781753
122 185 59273817
912 484 14153095
592 852 153889826
842 3 331143267
614 188 782592248
480 317 101976608
113 909 592882150
896 820 98691316
854 884 882291186
191 78 700744193
169 970 838821148
916 83 519778377
523 30 487902180
523 704 788303742
802 479 52675130
158 61 151604403
807 437 347955558
898 327 790469951
41 134 749035995
2 453 573320585
625 522 938239853
195 70 533439675
377 845 10442826
394 585 699674255
975 309 45129372
924 261 86572727
904 647 940040323
266 179 983309605
186 457 411161946
815 766 301796235
185 179 708000965
584 834 899185361
745 42 501599359
793 708 587718279
825 799 640065590
96 283 685257411
260 384 680078531
159 848 143791423
36 131 968018192
361 810 116255808
819 706 504112814
305 50 789928211
960 616 108971026
930 417 529502703
468 935 670134290
139 189 4353808
948 275 91898675
661 293 74686736
967 791 490453888
361 868 856520014
202 100 112187457
620 51 285837692
886 626 273838478
973 227 256743967
430 173 118480536
533 988 262530340
193 999 46500571
32 801 638419938
719 900 478701648
400 947 462376953
439 694 620576883
206 346 219377626
491 993 679280702
990 148 850823284
26 410 49718448
39 359 319376460
903 606 658768989
990 585 731288956
663 906 903075450
35 658 623847075
154 559 329649968
110 771 988080722
125 492 198195241
924 135 471705615
270 278 904925633
983 200 642717327
418 7 132772263
64 329 46437353
599 504 162927463
657 494 841789767
679 843 432314380
697 411 622307026
965 211 429229254
824 919 711789862
508 421 29901959
270 618 97781591
725 366 185731633
200 596 341306042
285 161 800840544
527 343 325706153
51 620 188657238
992 763 214766361
418 360 314735006
588 556 173442802
693 732 6349842
783 214 804315018
958 427 744170138
925 24 512517035
263 313 262121763
307 975 466633578
689 535 121848738
48 707 699314278
831 231 487176513
747 730 201302736
165 360 163350376
729 182 789690272
667 831 556638045
780 586 485287220
445 324 952587932
148 967 131477002
76 468 843476561
690 605 430382138
275 259 834026877
618 79 460165968
306 466 548915561
978 418 442052227
748 352 813297322
758 631 568138630
791 688 228018034
42 896 522589357
871 50 320086722
175 721 715859089
926 260 330048892
887 534 320848210
254 43 332676742
483 298 267342539
778 109 235011442
353 549 35657313
66 656 235392766
531 885 902200538
459 82 472593998
731 719 206673252
321 238 281616247
128 926 405312734
522 859 946362517
969 76 657583609
726 491 13561229
703 83 413799072
103 873 120283400
634 63 457437349
782 364 463382132
557 175 745254218
670 99 862697138
162 539 393059444
576 828 576165024
241 269 509314718
813 215 994982657
507 922 994502861
560 272 318776302
949 821 594535607
689 567 942566218
992 896 714413934
924 913 875039525
620 839 236226044
388 652 12882302
368 664 906998838
911 495 542170962
286 938 32909582
225 275 455709091
998 645 716694306
547 157 613336386
691 797 965307460
253 697 738799590
666 280 395692734
886 801 542421951
710 186 258789259
523 163 594076513
220 250 556252707
372 351 952714153
237 423 860056863
375 526 562610925
495 380 61710886
947 781 274819379
330 57 618227436
174 310 523075026
409 579 496689558
467 728 794237807
316 684 708041363
355 97 907853982
233 949 367391902
379 395 744472637
8 666 39271950
203 81 533261780
652 825 162083813
997 201 298527288
52 624 692677540
759 537 269553291
385 861 993148141
187 641 83953203
276 753 655253560
986 729 966694923
19 877 258048253
486 138 258678362
529 199 165339910
83 213 66588211
730 700 392179836
127 100 164517496
811 546 141384107
580 267 868583268
353 432 212941972
828 198 333955754
443 273 981737232
106 616 450575663
793 626 389278769
301 219 353457046
602 746 455802970
739 137 680036044
140 478 51741439
777 452 833946482
108 156 532039397
781 343 358294585
995 592 60568152
292 410 410338406
882 216 458858640
342 400 151553948
284 644 979053366
437 826 707081133
823 631 589635669
484 249 359148734
144 17 205593729
106 378 272431487
931 102 339278981
296 394 651988429
114 397 791443480
889 850 37205914
814 496 495827805
843 351 118382943
752 314 967844535
322 849 499933593
271 469 657836827
874 662 397850268
932 985 107416099
689 506 491725233
760 253 626925484
864 686 346169627
153 150 83270420
383 91 29152813
280 490 120774328
358 956 608557469
34 605 740865893
980 178 943243470
113 765 415588676
6 147 878526494
607 796 292189242
36 206 219646047
590 784 156561477
372 758 152892757
81 397 358179188
936 119 264707533
581 327 237290186
796 170 542477048
401 194 332366085
966 378 659471771
675 670 260913097
624 398 466522788
200 244 982013357
702 455 214209496
84 560 756112479
949 468 347489575
579 294 422142379
683 117 109925070
697 84 719148551
455 334 105752100
921 847 356887577
325 682 493901167
28 898 357963268
2 391 237462290
773 553 183136655
757 789 327326586
432 138 208429094
244 366 600478829
399 883 549180381
186 484 974754225
374 357 262533576
502 992 59080824
84 253 977013633
20 515 766181340
179 354 786124473
338 710 539501826
578 826 593803205
877 19 207009611
226 654 222640202
678 742 11299630
18 635 979503466
292 981 821239207
458 564 112939297
540 471 83784600
393 316 666253932
710 188 821205860
8 280 797830205
343 620 824820033
404 661 492546558
261 979 74471598
65 907 933695661
779 973 62406505
225 322 131852186
450 665 556028440
812 600 195152202
22 985 441975259
74 29 821075510
293 322 94797071
254 235 162889482
841 946 403081421
91 199 751777541
435 691 750348966
517 681 300318785
967 669 537541471
616 106 589272321
316 739 269547994
27 425 909741642
433 737 535784877
753 440 486148321
928 922 169744074
382 830 375081629
927 284 572807882
54 561 874277475
129 490 292814697
21 715 462318327
351 428 77656990
173 421 421945828
598 44 241619541
966 818 759226839
173 460 346708258
287 907 530196414
557 866 993093208
581 350 328705838
25 536 740154185
768 114 872579450
447 41 299474708
373 748 193904324
542 616 177909342
901 94 503338599
937 272 906314987
61 629 453649329
722 799 590063931
445 245 371143578
865 899 495008173
535 347 642311898
668 226 818726654
691 319 23590316
160 258 707836026
583 431 855595842
792 510 309166245
134 225 760554908
797 319 232047609
860 814 718087229
132 951 161506237
846 576 658879066
757 892 280617923
845 609 505379471
641 552 57051164
130 47 152861088
559 720 943829169
224 961 572794423
668 904 922988360
425 27 70906310
377 299 507594310
766 372 5048766
137 597 377537893
541 497 276312396
109 11 632292701
648 305 57557289
564 987 464114269
992 550 670765135
689 483 159437362
80 290 983091378
977 143 353577367
212 226 267145619
652 274 823950398
478 804 831399270
141 895 760041911
333 128 770778295
660 515 89045452
947 839 347555200
87 812 706790294
644 927 863661371
898 372 739345001
108 909 454629639
712 909 589950369
519 640 53051459
207 641 574494304
787 659 511366659
368 946 793892979
243 186 275090161
96 929 173787321
953 187 627400700
54 551 763542444
381 642 397625117
64 525 587399087
890 701 934432787
647 153 558980986
633 606 611773165
750 741 200052892
634 707 888551528
943 525 932930976
490 651 528419015
647 89 825000241
735 870 39086208
550 643 272503549
528 491 749246002
766 28 114599907
720 565 469604177
701 954 124989841
106 966 866344003
495 891 697007638
398 579 683797541
618 289 994463629
714 296 915390587
257 184 525541240
367 144 842670435
725 190 15256601
394 990 299924888
673 970 654050702
102 347 127884880
677 878 729009933
814 879 114003586
43 419 245764136
769 785 863180219
328 931 916463569
542 359 841916268
870 490 651322946
171 85 319808952
834 256 318191257
582 988 916579294
569 305 695520310
499 339 188369311
240 813 755502489
532 399 780990790
749 225 267560710
628 376 623887544
631 635 566116610
185 977 164281228
873 10 114765766
415 510 566853401
604 572 893221927
1 445 32107985
55 369 193559645
637 657 600956648
581 743 427603507
443 590 336845243
925 894 781929574
199 197 548924657
192 982 447613791
470 928 451954391
856 507 459058476
359 883 300563165
492 393 892747787
188 733 714082572
444 130 34939988
688 738 533556488
298 689 330762438
949 699 855669908
806 934 198620631
738 276 608974262
971 910 794824467
761 575 551836602
333 547 665245859
785 887 163366174
881 199 793382920
146 435 404644205
156 598 751798138
709 842 347332017
805 607 824010759
583 386 624485161
799 786 108036995
274 612 398160334
438 382 939525416
482 587 62600306
94 433 822503739
725 190 88854744
284 333 780762237
448 578 152340267
376 594 715099813
605 236 543480607
448 610 263063152
904 974 313577300
790 529 911993259
224 123 651295301
321 451 343365861
527 812 765030169
983 603 769180635