832 831 589 90
11 741 937045090 57406620
576 696 967102550 253369613
765 115 662697694 187465521
71 332 975407954 290148615
36 655 695111396 322792325
168 59 872881953 395193290
514 725 944160186 324960372
445 349 899480385 284475541
133 407 944541936 159227519
514 655 955601730 263115644
487 361 944160186 102829957
95 194 995052011 722825753
203 326 624296432 367551407
81 715 651979542 881948823
374 45 707537383 316231383
169 268 645686197 35503068
80 120 697269630 93099093
809 589 662697694 69397959
318 825 948606993 230264723
205 628 931114030 259085489
490 252 969834959 84879942
120 740 944932454 213957497
112 95 890536494 131781662
267 11 624296432 227019586
446 580 834285818 37587865
309 630 894165327 252297066
345 337 870413406 295728604
484 583 904694604 407241102
577 832 865280035 240870551
40 406 980418523 135877267
236 368 674875724 108589884
471 656 862195616 762102011
782 104 652190776 201681148
321 262 705838184 923138902
704 253 982974732 563675606
445 148 645686197 216570576
309 530 996807946 33986531
172 128 714165097 128600394
221 315 883674884 237008964
67 198 934072068 232729797
48 239 704016425 395095393
250 429 969834959 157186022
161 590 889736650 737878952
688 585 884560831 813349948
800 14 996807946 937791052
629 308 881849712 185233546
136 374 714165097 181732633
491 363 930375777 237412781
644 616 901227546 788794475
789 438 858210343 771264960
596 87 716617021 897438543
446 800 874052537 177143245
198 155 627091597 282031409
798 257 887786066 115133227
746 785 700627977 142086284
767 367 944160186 92150382
422 32 884560831 348703021
239 500 838664115 770698143
220 309 944932454 179944754
56 137 841722897 726956237
124 274 867727372 191840609
598 387 640272067 265164011
590 108 887786066 135701012
725 421 692960581 36771142
637 343 655285432 121047876
623 826 709351578 132958467
744 706 857758168 246514390
218 801 834285818 64475967
13 73 836204266 293149446
32 106 631855608 306316420
293 359 834285818 906048606
99 439 933101843 324515309
58 423 628668277 169469302
418 319 632636975 239796224
494 564 889736650 374997081
674 24 642387688 138624129
536 377 897700351 464778027
30 788 930375777 117922659
571 481 834285818 191429516
14 578 884560831 60889999
683 355 878934803 159761368
358 422 697269630 126032474
688 789 687285387 93710639
717 279 664138221 91723152
380 518 871997237 126102871
101 381 708883123 357739377
543 653 860356434 81275925
494 812 934072068 288040400
457 565 952231201 536966016
458 721 993980475 81903642
271 629 937045090 692335465
211 726 860843383 148973759
5 676 704016425 297991989
677 501 947699800 720039735
690 680 716289298 484744994
443 338 645686197 222197255
591 479 874052537 629820436
190 755 862195616 425963512
711 374 700222846 125527656
196 673 857758168 502923923
332 635 838664115 275977036
781 508 645686197 440276017
166 603 997302855 228235265
383 103 836774171 893972043
380 24 672473772 45983139
143 354 955601730 208583974
198 225 631855608 271939166
181 64 967102550 266531120
264 743 874052537 324233551
772 124 716289298 36240581
523 402 952231201 285125875
234 77 942548312 280034076
453 712 651979542 203357986
586 314 625716525 686787464
535 148 655285432 273608607
785 764 872881953 16489710
704 690 878934803 583982973
690 275 716289298 316062423
727 800 846943124 868660637
733 241 947699800 158044902
397 417 690388128 694569280
366 517 714648549 230579914
440 76 934072068 53061747
607 561 937045090 769323729
392 53 862195616 579032810
207 660 971171248 355843513
322 722 651538966 285698602
538 255 709351578 239224841
19 239 651979542 293344386
249 134 867854164 126395102
830 477 878934803 868987759
201 329 865280035 98786699
776 673 628668277 67307020
809 244 841722897 14267459
630 533 901227546 75085613
702 668 889736650 123038398
389 487 840864631 64152589
563 439 708883123 108625846
404 478 846943124 55721294
2 401 948606993 226693870
333 400 625716525 235245731
316 309 948606993 191528326
208 388 714648549 33389741
186 423 640272067 200137588
326 33 995052011 105060827
716 526 834285818 75634380
514 529 878934803 23244078
589 275 887786066 329087907
153 102 634214724 594421977
402 819 843039121 913281486
352 84 975407954 72940435
708 493 860356434 294693529
42 187 894165327 111525141
271 617 836204266 91511365
305 596 836204266 298376192
616 721 899480385 129018983
316 366 899480385 275469244
757 597 846943124 60044805
198 222 652190776 221767759
796 716 1000000000 298404688
96 304 969834959 9631192
391 779 632636975 742490635
502 188 995052011 251762725
483 471 836204266 647200866
448 476 969834959 213620977
47 273 716289298 106112463
528 30 860843383 314664278
831 476 944541936 210591598
284 70 955601730 226826660
67 143 995052011 829301072
175 282 984473346 551908590
344 752 651979542 803012419
155 381 865280035 197371881
381 538 624207001 276574756
612 631 934072068 291075106
288 760 995052011 83688639
802 305 624296432 31124306
322 738 1000000000 533262738
464 589 990479673 166594846
336 280 993980475 684679643
328 172 944932454 119572975
172 658 857404155 237866881
32 92 960097177 296062895
554 740 955601730 102894891
198 705 628668277 85549520
627 137 865280035 162494020
663 394 631855608 72457110
211 431 655285432 17125634
406 734 854547464 967866329
281 137 957447364 879855248
785 550 690388128 255198292
658 230 674875724 139742930
619 445 865280035 138402127
74 351 624207001 928029983
283 130 870413406 265309080
467 257 995052011 839972322
151 666 957447364 28415446
418 223 627091597 564933348
357 549 845936749 324022141
456 565 651538966 115407679
91 329 857404155 999481766
744 470 933101843 248622921
813 542 711858107 309257886
787 636 690388128 102781591
374 748 651538966 150286187
409 189 881787360 304443187
682 613 984473346 250236599
524 87 678370333 167544474
494 269 714165097 682372381
751 202 872881953 200527867
667 768 707537383 335434576
34 660 963634734 247320918
449 61 700627977 49725689
401 260 662697694 722275789
395 240 678370333 195125377
42 481 657160531 141850652
319 656 998705837 276150980
144 334 690388128 206078760
698 621 963634734 264358864
823 187 942548312 428408101
137 714 900060084 603414409
14 807 971171248 217239729
496 155 948606993 957280290
237 301 996807946 36844238
294 514 894518996 901969825
322 373 652190776 23648413
528 814 624296432 345548452
137 279 875489299 480236892
630 456 944541936 104942523
222 104 904694604 17930043
220 558 857758168 66681145
67 706 988067655 189066053
113 219 858210343 292171334
786 262 687285387 516850390
329 49 720157024 68396732
769 583 631855608 138965885
600 88 887786066 546601319
233 95 625716525 313492247
475 491 874052537 62660396
798 437 960097177 464971297
632 782 971171248 250608863
514 419 843039121 72719484
390 574 843039121 769928
72 390 651505634 184330989
804 706 948606993 245881158
496 113 865280035 183002491
509 643 857758168 196988291
780 86 716617021 259887746
120 3 872881953 971304813
426 754 930375777 804144882
626 649 901227546 288160178
569 659 975407954 242858464
822 775 625716525 62295573
603 734 884560831 875316960
302 685 875489299 295876085
283 732 714648549 293161115
98 272 984473346 834588627
622 701 982974732 147415873
251 30 897700351 320082600
162 121 657160531 115560022
498 566 659850642 76418802
45 246 635496999 380322093
447 24 944932454 36479790
624 18 870413406 227280315
750 109 875489299 179552997
104 449 714648549 16642604
27 331 684465807 157518755
160 569 835073156 107427121
507 730 952460336 315884831
178 515 998705837 366265484
116 569 655285432 239701203
156 63 716617021 82804695
672 632 947699800 47171185
600 297 629128097 181394189
58 139 940221817 176749329
473 570 933101843 128577442
595 164 857404155 319170376
503 625 944932454 130334190
516 296 860843383 275110718
225 205 942548312 39711957
311 662 984473346 216262565
656 327 983738928 311525779
76 587 973127664 41197174
49 331 967020020 236592352
665 236 624296432 475648864
63 658 634214724 307794114
452 542 979815412 90617654
756 506 874052537 269586264
364 514 870413406 88306195
652 271 944541936 485842510
122 777 627091597 131952643
461 208 957447364 241878066
554 49 897700351 203067244
628 710 944541936 146065669
56 624 667057499 221320087
527 373 944541936 40052366
151 731 655285432 542798850
430 379 988067655 27685047
758 40 678370333 663824972
57 112 978495294 444611097
640 602 690388128 233063943
213 309 681652164 923690946
552 514 998705837 243839665
304 477 976412175 199151229
287 616 655285432 511115682
666 798 872881953 191448536
71 163 697269630 18488834
154 24 976412175 898779587
2 723 704016425 36393239
72 226 659850642 744279078
782 265 967102550 17177572
445 577 642387688 607063299
123 151 843039121 217121549
268 693 671168466 233780452
567 633 871997237 635829065
219 379 843039121 195141289
524 691 940221817 142552303
679 423 945431541 211951692
387 404 716289298 88024138
131 105 659850642 937951134
545 44 708883123 44806578
806 657 697269630 15003473
352 623 690388128 87691887
443 156 674875724 96280184
687 62 664138221 41547567
452 511 894165327 324064629
8 740 901227546 221336352
785 2 959151210 149768840
539 655 944541936 159706318
190 801 957447364 88067487
696 635 629128097 484506235
100 803 881849712 328055885
809 300 901227546 805628739
82 122 624207001 208812585
181 800 996807946 619037200
194 662 978495294 3096675
202 370 854547464 110877559
609 742 957447364 948926550
648 627 865280035 609913566
108 762 692960581 88213399
480 155 897700351 34028106
534 349 973127664 4108490
35 436 657160531 252788804
810 610 667643121 109040832
664 478 681652164 978926586
216 420 997302855 119041001
447 83 955601730 62460635
477 622 988067655 97704796
68 393 681652164 52046325
673 630 883674884 309175005
415 152 681652164 130216445
320 625 851658622 332635137
233 792 678370333 80793146
800 546 894165327 19645051
536 193 700222846 262082538
51 340 651979542 299199313
578 793 945431541 67592300
616 342 1000000000 591166441
30 394 947699800 599306270
555 384 704016425 41191027
22 289 973127664 129798994
800 307 983738928 231449033
772 611 716617021 1680644
67 781 867727372 838245636
395 205 947699800 62708579
505 441 870413406 70102387
634 352 840864631 279248472
225 777 967102550 33048934
100 762 714648549 277648176
650 554 624207001 130089395
528 273 934072068 71257992
770 682 899480385 169404557
394 605 976412175 103333595
665 198 978495294 117445260
441 707 978495294 645070752
355 729 933101843 235475644
206 699 934072068 26371753
612 300 930375777 240927252
816 795 672473772 253021607
393 546 969834959 165227011
192 636 687285387 638643673
552 121 708883123 285753570
54 280 875489299 173568456
574 107 875489299 141361051
657 6 632636975 167956903
749 655 629128097 405904628
199 43 978495294 144907939
602 763 947699800 150618901
32 157 988067655 76949014
41 456 942548312 115959158
157 453 942548312 237681606
423 568 904694604 14453637
104 79 959151210 148121063
7 794 930375777 136768389
124 586 978495294 230378427
183 198 716289298 731097615
94 787 645686197 17632221
825 827 687285387 233564436
563 371 645686197 24778982
553 548 889736650 197866513
70 368 714165097 488353915
349 320 971171248 88723854
416 604 627091597 42058390
135 593 700627977 525499183
231 493 843039121 281913283
204 423 995052011 255574393
825 148 988067655 897222039
40 146 978495294 196989295
572 8 631855608 55248732
522 290 875489299 55872596
754 225 700627977 882290486
473 428 937045090 134557604
799 129 684465807 10370642
748 516 960097177 854302961
552 765 711858107 800365618
413 72 938413869 200345636
800 42 716289298 8387604
588 364 711858107 157279262
243 86 931114030 498316502
502 185 651979542 724446871
206 49 955601730 95566676
581 138 979815412 36344714
17 218 655285432 160948339
670 542 862195616 277843176
135 32 634214724 231099244
29 721 937045090 297235402
273 125 697269630 233828700
682 150 674875724 180044781
178 76 967102550 950165624
745 445 845936749 278168947
466 131 637548722 91714380
671 42 662697694 52689245
524 577 700627977 11300299
730 95 952231201 278318686
236 272 662697694 331639986
514 424 998705837 456888825
466 269 948606993 218015363
343 677 938413869 62389558
36 396 887786066 162023447
372 218 857758168 145417807
529 559 998705837 523827405
365 403 903127031 112644362
436 94 834285818 115753914
706 671 651979542 91691491
215 190 884560831 503682917
747 475 720157024 766796518
555 56 990479673 740463313
206 417 857758168 108713347
639 263 692960581 213318430
514 205 635496999 168655981
119 605 980418523 73349143
259 186 628668277 415684548
797 494 887786066 92872283
775 744 952231201 56324984
523 205 640272067 257974949
142 505 938413869 540306993
490 641 960097177 403345859
445 225 872881953 721424982
431 278 990479673 641667343
336 233 632636975 300802942
341 405 938413869 316954014
173 186 983738928 972367521
76 610 887786066 205351380
799 678 897700351 847865795
489 124 716289298 268036448
10 373 628668277 957995425
281 689 934072068 29904483
43 577 857404155 609082101
444 410 843039121 253099787
516 227 937045090 37956877
713 320 990479673 162733908
754 400 957447364 329170660
36 753 955601730 278635652
201 450 671168466 79635830
148 435 937045090 78776394
171 359 629128097 327778880
138 489 692960581 260662259
479 719 867854164 287963111
504 165 897700351 2014860
292 508 998705837 4102939
739 406 903127031 229838493
323 171 904694604 42678160
586 490 705838184 134237445
523 743 709351578 287373256
514 742 634214724 231294632
598 488 1000000000 437616974
14 676 945431541 69910000
203 270 969834959 296893416
610 114 667643121 64236031
530 95 640272067 296987048
820 638 652190776 125277292
147 303 901227546 77699685
325 431 899480385 256227623
295 824 947699800 177960510
590 330 857758168 177860869
165 360 711858107 587024389
312 806 854547464 120099620
662 479 631855608 257953562
645 465 672473772 226478699
188 461 684327196 325275974
401 117 960097177 272592779
723 573 690388128 11409245
45 427 659850642 215669983
241 737 841722897 346153907
37 44 720157024 243207613
528 738 678370333 495445818
283 751 951321036 90944987
658 487 860843383 834939951
197 171 872881953 123656999
67 271 642387688 244216411
425 97 944541936 470653087
291 276 979815412 69646191
396 403 835073156 276482695
20 565 890536494 213255828
553 45 704016425 725868854
531 344 899480385 736823680
445 425 836774171 17255490
236 60 857404155 3699898
752 67 700627977 143543091
195 122 674875724 287146700
69 7 671168466 92897177
492 628 878934803 269074226
310 432 993980475 137853739
55 756 840864631 233984659
667 405 836774171 766150107
760 563 651538966 189593293
275 806 843039121 580387360
75 165 664138221 301575877
681 537 672473772 19362127
647 807 930375777 127711855
238 663 720157024 299668224
130 645 681652164 107092769
681 621 651538966 762425690
431 547 871997237 936135511
170 659 951321036 872169839
258 1 990479673 271720113
138 132 875489299 679394835
205 24 858210343 1136773
31 751 671168466 276298691
731 723 967102550 861705592
176 742 889736650 286121601
359 53 624296432 68759587
299 611 998705837 301033280
298 13 945431541 55224607
715 830 629128097 290472902
229 670 903127031 149348316
228 74 841722897 198825579
642 807 843039121 310039356
610 340 657160531 638841
496 65 899480385 67511101
480 461 963634734 119121585
103 182 894518996 159165874
210 259 1000000000 103536939
252 451 951321036 332756900
787 599 937045090 106400342
147 742 720157024 6143925
790 487 874052537 294623150
414 27 888115342 576641528
589 592 948606993 288787506
561 549 657160531 42544710
633 831 952231201 635834902
169 65 858210343 978793520
471 127 894518996 991418380
784 219 637548722 761786304
221 287 899480385 126086299
831 62 980418523 55553534
709 11 930375777 15240630
262 44 969834959 10541626
718 98 975407954 309687708
608 324 651538966 62510635
86 402 664138221 263517903
673 245 674875724 167876483
828 513 860843383 180410120
328 28 628668277 296408842
566 385 903127031 186123821
67 386 883674884 151957299
567 84 938413869 43325579
797 266 931114030 8142353
732 85 720157024 211859873
7 754 687285387 337308434
177 703 667643121 403691091
180 679 887786066 181659544
16 657 867727372 128052299
62 212 857404155 805883682
554 149 697269630 2059766
740 473 979815412 48425748
72 620 651505634 529322040
706 385 867727372 36835418
421 23 674875724 92083151
721 669 624207001 217668076
489 76 687285387 204420842
275 614 975407954 271540139
196 536 651979542 304778072
53 724 871997237 246618924
236 828 881849712 85922059
509 385 944160186 294998647
575 310 640272067 196093198
13 380 631855608 282710450
262 519 648513099 728281177
246 217 637548722 254976191
787 124 711858107 223549373
776 191 955601730 60700496
118 261 959151210 283626573
734 50 714648549 741246759
584 542 631855608 35867053
659 90 834285818 259665260
601 32 684327196 132257357
33 399 854547464 44745415
423 385 714165097 127324665
309 795 845936749 46632520
334 497 955601730 298596082
337 2 979815412 48378349
817 510 640272067 137852724
475 739 667057499 913718677
205 309 834285818 163292277
560 610 642387688 139714982
547 209 865280035 232381517
660 332 872881953 127996921
787 59 889736650 16529634
699 52 971171248 797455430
544 149 988067655 889679727
304 638 711858107 810230844
335 181 982974732 100927169
806 695 888115342 518714274
541 130 850400260 859986370
816 606 697269630 229735359
167 283 975407954 21918295
227 339 711858107 648361215
734 282 937045090 23571462
765 228 707537383 5213547
159 211 871997237 933098655
502 360 952460336 123317002
671 545 980418523 845468909
696 247 969834959 282018601
497 701 624296432 34927339
269 675 695111396 75276857
779 778 870413406 328901699
186 164 708883123 261668350
15 285 674875724 138079095
211 721 625716525 202717536
635 329 976412175 210101679
314 815 984473346 163091112
733 754 933101843 241819614
402 92 899480385 44814218
130 396 711858107 118174275
412 24 834285818 772404980
649 577 860356434 264810830
484 25 901227546 460543815
706 703 836204266 329483720
385 26 875489299 747947113
302 633 862195616 556395903
534 469 998705837 25968007
653 660 875489299 241424112
276 410 871997237 607820413
700 291 708883123 136204812
739 95 627091597 982960051
416 624 632636975 687643725
575 423 979815412 909184489
608 332 960097177 331955871
557 452 840864631 237999823
34 525 982974732 99728406
390 410 700627977 317048785
817 471 645686197 63732553
239 155 937045090 192953427
773 656 979815412 300859571
633 124 942548312 214327490
794 232 870413406 787742764
582 671 664138221 53488690
807 621 695111396 669903692
383 552 983738928 42730095
63 552 692960581 317626482
589 198 940221817 217909553
237 773 655285432 211820516
455 462 678370333 192493902
184 221 931114030 184934016
496 359 628668277 959287653
561 385 637548722 1722105
317 758 697269630 222168691
754 355 681652164 409758770
141 577 655285432 80457353
132 532 944541936 126672546
799 689 993980475 105785332
62 818 959151210 268545162
617 463 836774171 10269712
824 138 716289298 536303476
327 269 998705837 673491558
206 63 903127031 507687025
762 287 944541936 248027717
429 467 887786066 125231137
471 774 967102550 161306074
11 574 903127031 28625029
39 367 944541936 333118918
633 577 846943124 56248270
15 646 716289298 57185164
736 347 652190776 273732884
401 179 894518996 199762531
723 579 628668277 201002253
115 757 878934803 532634486
336 459 944160186 878027919
145 646 934072068 195659627
369 410 850400260 94486551
88 235 857404155 319658393
569 677 996807946 805751646
598 499 629128097 216391662
275 720 952460336 577235435
577 152 648513099 36569878
67 2 937045090 186257612
186 528 995052011 967212802
668 744 843039121 21681296
88 506 894165327 241202863
445 434 651979542 493624691
89 825 714165097 201815161
257 520 948606993 12530837
88 495 888115342 224658886
313 492 845936749 822916865
118 206 883674884 608245899
472 395 651979542 120823898
137 482 659850642 297233297
242 150 625716525 293356997
126 546 708883123 892849526
248 275 627091597 156923005
567 407 980418523 70551021
109 621 955601730 181800633
452 522 948606993 407777638
63 688 629128097 325699643
783 766 971171248 957872156
759 584 997302855 88458289
11 306 952231201 94309790
594 788 960097177 150998424
676 21 984473346 316602292
319 387 716617021 214081074
474 1 940221817 284299700
133 442 969834959 269003244
15 376 851658622 241712793
521 83 854547464 244080792
554 763 862195616 76050981
24 618 944541936 202048253
413 286 690388128 108276847
36 574 988067655 176727195
694 646 884560831 849387585
721 455 700627977 305156959
22 444 657160531 131024836
556 823 888115342 159909216
684 726 716617021 138519491
346 665 645686197 38291068
813 767 672473772 886267155
453 38 645686197 273287197
347 273 963634734 231711261
224 671 651979542 489890939
528 215 662697694 96528886
428 661 845936749 123173972
551 504 655285432 24238615
646 673 678370333 279317647
716 456 708883123 801553685
140 791 672473772 311962839
263 484 980418523 56090802
362 38 872881953 20798722
485 352 867727372 215979201
214 40 944541936 69579257
353 178 671168466 331441333
760 409 938413869 111662505
562 170 681652164 55104456
174 406 930375777 328455552
569 124 838664115 68862524
88 552 692960581 280238322
37 486 995052011 325114532
813 441 637548722 152498463
382 504 894518996 198205008
327 200 990479673 61438670
326 283 860356434 125483770
411 575 951321036 83244626
534 1 998705837 852524032
765 651 716289298 957983669
619 66 862195616 223858958
319 375 1000000000 8646500
766 383 836204266 33884017
348 422 624207001 604646951
356 124 874052537 324500971
341 9 899480385 139600746
811 731 933101843 34772218
148 4 624296432 267218739
807 540 900060084 203948417
791 195 672473772 849222386
271 452 692960581 116577606
174 686 944541936 260927019
408 122 973127664 214772073
124 234 845936749 307034488
647 158 674875724 62014744
583 476 884560831 187770531
772 728 870413406 37793937
398 545 657160531 256905574
561 477 835073156 928567678
319 706 659850642 239262552
735 149 687285387 114348621
350 13 841722897 14134948
110 555 640272067 547725016
12 808 942548312 184064739
777 768 957447364 61499683
468 742 846943124 88517388
596 78 648513099 214463532
721 589 700627977 311695494
821 552 947699800 179322383
210 692 709351578 219572455
503 697 963634734 304904557
121 454 944160186 145595792
93 542 900060084 172847161
654 701 645686197 158307462
744 771 933101843 289452588
21 761 631855608 23392046
20 433 867854164 247617550
805 322 955601730 305964001
259 615 971171248 128498154
738 420 937045090 300452533
222 555 645686197 24082602
730 682 851658622 311572878
439 546 624296432 244203990
12 340 872881953 2645634
829 729 624207001 140959594
779 636 667057499 895091568
186 254 857404155 13435683
389 378 901227546 652498142
460 33 942548312 82923921
445 512 862195616 128217298
708 734 629128097 120496068
287 102 651505634 81841036
277 517 840864631 105163454
209 46 933101843 6112031
214 134 860356434 236487082
178 256 632636975 133688541
721 227 894518996 257374760
540 111 1000000000 809821683