592 403
746604030 483785688 782698676 978736718 873043918 669999891 503087625 225994179 683232769 338396203 654741835 836245226 688760236 197827440 746779807 247833456 760902014 926685244 366055091 597002922 232813427 842713828 373035374 184765980 848108342 239513832 757021443 663910143 188767282 490194288 868504348 892026613 121920094 940795021 748590303 119309111 434637101 469125246 831719645 734930490 489129204 882321405 314062906 718621614 709246407 317062329 208696188 651726077 186566711 514256739 987844712 965743734 419342133 709411427 681461766 815021290 421760080 433849894 286059528 208838669 785195517 537523006 583125599 430452796 136297996 726795295 601058543 232221931 369668705 714383325 2433549 917859877 430664593 573584174 577973950 939121759 422876030 842231743 196306564 190904364 13754527 376029863 150361298 664344045 2151807 994271665 148657307 916147786 457177099 275984769 894643288 847982053 887214158 418739707 937898913 88353075 580061970 59288070 883287835 135137264 705083961 208313474 249995085 204658730 839797960 344332712 934522018 976922013 40244204 825864158 611595339 98096615 159795226 48219190 183170214 4469718 175718416 935944435 413485014 404911783 538201854 851952107 929804115 889335101 402811785 921963914 552581294 863726232 226230991 137088146 251000521 951659856 692572684 898479594 950015065 673051441 33640435 960247919 569380667 170669469 650676940 916771699 427774696 210908768 815894190 244607983 535333310 269216714 664397130 790481161 772340027 556504071 807634008 951610905 662845050 375813660 196192987 317963 244203157 775630524 830574985 143542837 195779517 238157052 664594921 955675562 898225238 874971674 415662898 609844490 916816612 849039137 927903481 173872545 244414034 50190717 940689965 431921466 789441287 609411080 718615695 206755612 707259636 480884676 796405864 920861241 635111265 496742274 968862596 734138152 175206678 185890251 795284150 704440224 754618540 531973121 398388754 634199518 434405675 314181872 855506839 747093149 952420648 670092698 188005092 524064038 78827432 598367052 823331423 304575447 724355608 397252570 729550391 282202132 658230873 794491593 787684177 88445847 458584299 110704456 343217354 971426067 964188001 173530981 941371697 78178804 49336060 944892164 86132644 38442323 416839919 273402546 41837685 515912124 859246646 513173837 275039105 386892093 689688919 325646403 870118982 309617165 588751337 389353345 1797203 589513309 338092919 51133071 187947729 460820843 130703392 317181975 618560192 989519036 615412406 988747063 918951608 136356586 603709315 330805950 768636002 932254679 914822057 383906341 916735692 492084953 743974652 685518203 752401756 624183797 260104593 416238747 57316116 650079054 627859957 233261287 157794018 68650883 678473028 741558001 671617192 223188254 251250776 268373408 488941276 924829083 988074833 318468862 395338997 749163707 604494259 745254389 673494916 480550199 321431551 498690891 300138574 283732653 212658378 258469049 719167808 965756105 889226570 204629153 686680029 853588036 545811525 227041282 434840566 134522983 613181409 718951304 941400329 521206249 979810924 339393984 908171553 145239604 580223979 632191691 545610771 135309494 576280322 97921837 990539654 210845719 119992616 587923161 807359142 882288730 531865659 596615263 636778848 892257514 744387564 30152151 788310257 965093051 270250252 282629286 861238522 867195996 669372781 74638991 455743488 217628819 654501601 126075873 576350982 891026104 805814825 440545508 54584047 480659865 903430878 276713747 745596113 452505251 112333624 139659435 226846115 270544710 620279976 783360546 996026157 372616031 394430479 605109787 714947532 701045904 69155785 508274623 590170695 684641850 97646130 111805696 457665227 348915410 366579186 144448086 468503841 843148459 61427563 299862690 402624641 883110922 847655386 205508392 418893815 640901331 988120423 166756717 26208746 2189333 6109764 158286987 590023281 636354206 39208643 636053565 559431168 186937160 473590289 237050971 490993353 788995742 585246585 4198974 506015029 431599450 904652713 24986919 253693412 67727786 342071287 399339785 934170327 34015576 852618897 848142958 558094586 152875231 493392433 361443575 521514492 949182307 595677858 830349343 36618895 468330266 981364197 798447476 117929169 599095562 457975826 196723596 568160943 799021674 397743745 79214259 527599208 610500363 122141641 58280289 991006933 67807776 451680349 780780829 749356624 804020149 452062643 3462766 294531529 608779640 819854642 217805841 797079318 336544875 782857131 985580712 747405262 564873346 417054346 359529379 505744620 258915669 365949054 445833152 387271354 567595284 541735732 46515953 426180884 45515718 978337413 219367256 874582570 741236338 128803554 466851526 955633294 892016050 337265742 545091762 130732266 813857209 526368135 937566460 211103891 842054337 485139761 305685713 542524403 294933673 788307208 101147339 875526347 344605003 507986327 48451610 867527215 227286878 337325316 711184455 47501990 739437322 852706888 268670360 852758442 947452561 120524282 771072172 641028099 195430663 214101406 954863726 622906637 92594401 412698861 508745776 356961447 699702720 637795156 239159034 344613012 196563599 256275400 189538053 115193830 543697718 715061444 392182829 571506948 236515652 464129664 572393378 34714521 967716257 210183830 232797520 711682848 912561104 132122796 987657915 295823950 75910896 182325369 116338384 418759262 941741029 397351556 63749878 197644830 339571974 37610042 411174157 958948543 879893941 109940709 404998663 715972606 47618908 798345045 66600467 17706111 916094904 112891460 713341949 786104675 894689908 583655186 729544442 873488976 552523484 795053450 633866167 502997042 970892801 738592806 452490003 437362881 584692925 439174398 632095645 683839539 78268406 200397324 48868183 781693538 953664794 300653037 895278105