480 46631011 807620497 658846264 461243314 658411884 407519025 659058680 181930527 411783265 851780337 302146669 675094108 661533056 273426855 480992727 806660526 199660909 455633326 329538059 456641632 299919469 809372658 337999210 352975560 433501741 611740704 780945240 630919498 534048894 207916010 55629160 459557126 699174214 881111831 983400148 730955911 700352555 63715174 459568002 268837958 847578281 111477935 864297552 141109337 635179189 343746914 483956815 704096019 142126750 883660647 80295009 877398100 836201821 851629843 974130389 832665893 414207384 748870695 562203075 459556988 815297735 161647790 341888210 479304400 927086996 241476246 934134781 111369745 256619516 285770674 13165700 745848444 675463164 13807409 834195751 252720740 735743992 723676710 857481788 74261220 879983970 783866182 838377571 3311328 831903644 332377737 436395810 290796200 739995928 274176512 75695565 790694312 584815348 565974490 555446685 862056453 982206693 736808171 936150402 747603759 584544375 847212897 598134520 747666267 947683401 524936332 526866161 883832786 954883928 222605405 84237177 702870914 666696868 989905794 759844852 870325713 781320999 461250043 616205376 966067503 502656115 824664880 3995750 490420220 451712059 862178699 666304652 887130129 57553122 667859407 762687249 913822373 632842994 320952966 148550434 156296233 955730004 804004562 303333243 981862631 728636282 608063659 547154028 70784358 671562595 772933517 163016368 119165110 223515443 254564773 241295784 70933304 380932581 223386913 306198561 660075117 81259859 16146598 687569164 976698598 340907083 543955392 756371345 652354945 460683069 848812496 993784650 708100546 877259329 329923098 54287815 157589186 31251560 700542004 171614169 302603470 262080014 643793008 903575671 292449634 435806573 615784 235393401 321575941 727789823 988475490 948335925 803303100 210335034 540547986 713792709 69497534 969164853 837380254 463004550 347515935 798845536 346139504 705962241 991375949 257710799 80609003 371551758 493557913 248371189 534599992 717599150 277478441 878467825 184425909 117879208 582485303 294098040 992586972 75999085 393326629 60802990 494479207 997009904 805359667 831597814 639561373 603326317 634498780 918257290 762622132 887177904 775863567 702931158 273717280 845036819 58247215 437745425 167360649 368324925 309100237 673346617 939836126 310441513 871646632 665914871 12432726 228382809 964941921 7571251 875958309 843601128 558008174 555280077 745871470 833407131 609136443 646164076 791693410 939444787 343871598 242978765 352495298 947680968 258369087 978994744 123851027 776120248 605685267 489969895 759374149 461454827 326521545 185617638 289314570 581266861 938327230 57927781 849776711 132592737 201083110 3736725 556475606 428955369 138429106 895343960 968829847 640351316 841238178 184605926 978842598 581161495 588237494 578555797 581868600 748675331 193075143 665109919 700923106 547383717 978511252 258426570 539441322 257210398 422753566 217667271 17564602 44310817 7739736 528667207 138125570 101480874 564254333 391068778 981287024 166396916 759591008 232029053 697883958 41995989 513723980 142268395 16990941 533991562 71072881 4666157 419906433 972484072 427851847 492423530 473981552 454508981 639731235 90508755 703295823 366192132 318127884 489419462 234657133 730685272 419132728 938415943 245814946 996322630 848672969 149316425 387971247 609702310 561767387 9394099 475923366 321137924 409626565 842918824 852367449 154316692 252184768 132692224 565246998 670694315 458892068 982762597 666325489 591453313 783450644 233703577 310643988 590746646 298261030 488743703 371327560 320377634 917245598 580604820 332120943 834390815 735228989 929043876 58899394 251144575 479978707 257695431 441413839 70627518 840409021 345516497 164958321 781337132 144183365 626358581 756613338 338446394 844704889 12317837 557285231 795899994 216559520 540959164 500955574 301424074 67287634 591253601 568986010 418651906 188869008 985678142 554921885 761284859 299643255 856562227 692888326 860268901 792014287 686936493 99713121 881182828 612247074 946537158 73079702 735745768 356804375 734100735 631046772 529270250 761086549 927305946 334177093 116035524 857306327 852255791 999866365 952430615 668075331 158057471 586315500 360763052 853118169 311802226 52550332 80287931 302832505 479156351 76005114 548927992 815693840 138735024 140767860 781375984 868166125 382993333 186076768 560799042 862375069 430686361 693226281 638074120 979066040 674571587 691736466 344354315 820513189 964815295 863829164 23841698 98550910 237669838 629301930 126555220 215115153 67112238 552567969 932591923 37782681 734523993 937560155 655362041 103120533 653816245 394960466 52544947 661345767 284145863 910718465 939573894 634207914 730376568 644553019 545692359 38905063 922162560 440615119 341329394 166886104 435048479 146949859 298324766 656445813 936160771 349890300 953979048 468727511 929087041 522148546 176688056 537566629 470654300 646522342 646372889 504656856 290023918 694803533 776381242 203003352 582762850 412062261 189227488 882067361 94388010 78770031 98685544 862791998 591726142 571827296 694747350 892218365 481608796 593074950 10142791 867603081 776958479 675438984 1035912 490700502 190966972 547996595 821836162 383494898 373050646 423634282 890480075 748280481 882312960 692564862 874133098 316145096 864684355 25111304 49777477 338221598 408461111 354899512 261296095 834005633 209545613 437218705 509496211 874618442 673922178 710182158 204623830 93002294 348807926 461508862 43674852 644226699 669918578 756459076 61276207 983515497 492728931 203138867 392945568 152836896 684791329 890858172 645709155 686091133 81118468 835753018 175298751 486429098 838048375 289435381 381567223 266142739 818863710 657053634 354527010 417806207 628181008 671755959 765254563 764726802 896519759 715331246 708074270 15204843 253313836 844370494 765253533 935074997 623468785 158818734 48550305 605153155 599615619 231874838 47007109 708403320 971546654 397895057 160381912 795978669 279515762 976112373 680385417 539128077 408808577 285264860 80532180 948981949 28326450 385306796 970354085 224716442 397820459 892894210 848977984 650489777 902440260 194483634 380205801 280113246 429523876 218501020 472053481 625340043 27533601 217828051 791400410 629827501 948030356 104938303 578248886 793249889 400582094 104872835 404312888 353317206 42571984 919165638 6200384 994292646 234138230 498914702 938896632 558522283 857171392 771388275 576050991 27274054 413727890 174005831 187647727 801957706 702182691 511799191 516212777 333633559 755141724 995844942 466828959 209868449 856293123 282626541 949517929 587668131 662296726 960005525 145991696 361770912 21677700 918495542 30245621 587802433 335154576 904775317 824476963 347050180 866834819 942402580 828036010 413951807 227323585 380830329 896814487 443343672 240797681 508145021 91307549 332178577 597618562 505478638 376590439 855025069 133438765 348628599 121285445 82660925 572286708 906892062 825397044 511000350 47833969 804654835 143974737 965218017 909996308 789991420 149395534 74012626 415071025 217415722 934333649 883584694 977028130 665994793 332286486 553192411 782437912 775792894 590433559 707616032 98230713 563559033 136232661 569190553 351589633 850539776 783729534 142724146 929252939 527362655 106549358 717354907 26726146 136712080 659068646 701643755 446367862 719965398 534414844 588491848 400958203 858733217 444043337 27543674 731952189 380249053 109423838 562716650 724176208 237940743 638952899 809409771 884975267 293658102 764336787 78440862 869240466 288363543 848990816 106026495 166250279 489570032 126932029 140785646 350247582 697065783 865204437 583405259 151538400 380615601 581915820 744714335 828998031 378271410 814844643 406636262 495344719 110862987 330784492 253625812 993777580 199208643 101210702 65424765 2738885 796312812 585376647 30754476 940367312 345877117 532699194 776452207 213512882 932216864 281412749 387576871 982375091 410503467 193844696 607489158 138740622 880370228 30576890 367649457 913678466 997631933 978392457 68670562 513959866 163797599 796447264 870854322 169709999 229834854 465382051 276179898 321790665 107876970 543996577 264357650 365734705 520768626 515088881 255240209 372760347 563833721 280364011 946347822 24618301 598132993 397410252 595429798 553927843 254916293 232464280 773018598 916255272 862317059 73371424 587505469 647182379 619062702 444606565 316266522 744414637 538039755 199617838 5449288 156921060 823918584 970236217 142792308 666127629 672531262 105124325 896310340 517927084 764721544 220758641 955410491 532562458 495267132 186484333 933455983 883387876 547385515 101670166 856013494 607950809 517735944 263861563 335170914 273276267 205901554 32424222 666831358 548326554 469868181 918601317 150002499 583578661 84786458 625834032 687524098 800999952 407615209 675912079 542765202 360926896 898051615 159079425 813508260 621023587 990466986 748413068 513311868 394698428 68869457 434025766 750099758 445275885 285421968 187787421 768330876 247700539 284370479 932899075 911529314 797992316 671308036 411292109 947570465 121954541 238309308 602017026 984254839 126234240 201551500 667579418 847409175 483270472 886706367 251935214 743232633 629010151 981303452 800034331 983961061 273474241 914707909 229885221 906697284 992627124 92480793 578960330 81216232 846893147 214812144 483376429 454318441 810200988 306372403 467264309 203372125 775628962 765505411 709304860 691928909 721354386 835950240 502818045 616935104 602171810 228850371 944593985 179202393 374080664 202143219 540432363 431275265 892201777 618285676 435558797 893555818 327127040 924337420 163200488 164285657 712052748 217313823 930643571 532078910 819090889 357541672 95491607 324689768 169291436 553685916 453035226 26985000 968383485 508519929 530617232 810690353 632886854 350505801 110972735 272587215 179328552 343173083 893587363 572309104 506670988 999561148 571749385 48330492 704797414 951092269 661841906 662327681 564195981 844476864 573790578 116993031 722257302 238060206 540681054 706777520 655081841 948663858 923138625 238032757 583028055 224858885 299343496 703323600 890234859 772863691 506917252 131615926 949808311 775674624 780798646 357738921 417679875 980050108 862041657 970483835 12881104 737892731 446538957 252346291 360371886 913144094 999113121 840869585 357013304 551745303 43232615 575651062 336897719 689556837 557365188 491937752 140251144 618169971 123319874 943862758 980730088 725548553 21350423 594062947 548465932 370936706 614460933 389481079 628739824 138690943 853946032 870938683 14445312 702201476 749075782 273599143 903392296 517788518 59426756 650087852 229331728 742360353 26098135 403993934 382948828 275803232 557775903 970889255 361256687 495809949 39539339 95422220 962790565 191179440 762862035 676726497 362543624 213291299 207309446 210393406 722395083 773612564 296452823 125333696 167241027 138031604 248674332 403002176 888146260 572403303 232428884 861790699 428336596 612075900 596437610 779269693 441018990 950932373 718247718 998167520 35791958 552687152 976063559 945672158 17413558 607521154 606064631 772460488 681146197 300185023 866838692 855693350 462152992 488813969 83946104 977196747 589536901 278917618 627742 379755676 135244352 635255471 347124641 344373132 354613414 69227199 866517130 56863171 227225113 884384596 350584531 725674171 920337092 727114188 126149990 124033760 241325690 9314807 518405597 533715280 682832751 870919129 484586306 546618509 112035659 807448591 456700913 733680028 213700430 605641888 145996644 630432301 14197844 717269121 893455824 824807604 552246158 183647018 498060779 167736067 804139219 295007479 750549818 382549337 678646838 118986196 7307551 71974510 544279658 817647984 343173325 385501783 175399338 208473801 683976813 823032007 555986650 66515943 783027013 936316513 323819706 900238572 847417241 294133253 361780248 917303373 844257632 782017958 289099402 846010917 566318859 813825854 164383047 936761278 665666575 492144089 365645872 794515427 456639155 293927175 487687410 899645534 942142517 549991837 165356018 341130833 112032756 905632162 112326410 501023375 338352167 415672192 757815478 635010291 256155660 232131643 920553220 316888054 515275874 451817627 660814912 208047218 872542727 370522557 322788718 368045657 861394916 344526582 858255549 827150942 33517831 920074658 827952322 82487018 422934011 185919475 790239905 126281837 377597805 565800579 742284134 615179122 660256339 560273642 647008748 804125495 853873626 206434003 766650419 366903227 238189941 140271267 684945881 436734531 50270671 34061574 937111088 397704594 330786989 198146484 242312456 699564552 328788228 139772037 858269638 862137756 161410882 675093947 25247179 611329306 260749833 93788577 179422900 307556728 495202211 798317407 837686220 407460339 833811241 985954788 138077748 403907312 839051205 135824177 715557173 738247179 21102370 736292501 206191516 568680225 231194693 122106128 719375198 104356101 841339915 359813756 688180752 552400071 207213931 682663754 194039118 871548568 609791776 503993270 665917922 286430172 530112730 527179144 323444295 219699219 49100551 833414208 12788743 426401855 3211432 323723884 357013014 596758560 544805138 824357697 446104604 599314540 687260208 543743000 276683028 406151786 789234358 785877888 540834482 484963763 824283411 957159030 62505165 635718171 336838400 370350314 752364637 210960559 983402829 44293067 367561500 829559962 726533255 31103268 765409705 702595189 467380234 637203359 450732118 850186266 53417355 599108070 270594010 581375251 60208951 432184976 165248674 919453607 497700155 309697136 890859300 12408509 771008641 978454238 591949783 614280464 138683162 753302517 833773732 90084375 759519498 618848983 280097812 565390538 515434335 512129265 141797845 800511527 112414781 132815816 933842131 671932478 77749951 700343112 66643372 777439387 720855507 553070014 340881862 143518174 369911881 47844576 622987254 978445996 214727771 127762758 716151150 173440533 515899581 178429640 757753525 955680817 48010560 657348801 535717865 99767746 61430918 944263301 785943533 25435685 22703564 41944009 383802003 536373824 768680007 372877652 393069993 144600318 180480968 721651170 652882443 567235086 56645193 361106421 701051259 591812486 389596129 666027510 95557985 622309393 39043307 492980201 776685432 895357740 177379878 326976664 794127260 899713167 434831734 522548727 600096771 288853913 949188692 47611843 234935593 564781271 176412445 252947718 980159550 483374790 396918749 701835723 188096799 46905391 49373516 945401097 811079496 575708534 6148077 534030246 757941762 898919018 873385968 704365794 294185523 291125003 540498796 552617914 383861260 289560718 589013239 922081798 250855076 154239104 261304267 407734981 853841561 854632396 283320276 645686829 988562131 304275756 665725168 128335320 768517641 942142930 28728186 465605313 963326400 386345267 229481665 717190980 321888842 960373452 645640625 123120949 369811825 266879518 167024369 802095214 174757973 925085780 544113145 163170451 546721479 804039012 366272828 45662562 461679132 602892504 115439349 693225180 23860356 235153026 608686606 756397230 67386834 152132437 299751193 977195148 169601905 739625004 693989331 957905089 390765883 634819365 421319793 729568881 95011157 530567619 363397228 93822308 471324667 937350006 1758044 362171156 991939842 291760991 333679977 11565168 289057428 86183990 313680508 438279046 637622420 522058924 111325793 380679810 757299164 941895398 16657902 777066659 381943127 294709803 34713080 724047893 47719528 692777372 401826064 936497781 696521716 770257703 920704677 642352874 167972100 225105557 315888627 29110081 91317049 6195571 979008875 275878393 444588509 321160902 427075720 48140507 574756006 281193878 843713175 853707164 724582677 407875845 642539173 749088390 671188058 495672599 882792672 913425974 316020725 365077008 177006384 825461631 500742431 193899918 515988179 759450300 464619435 584596106 905350842 461319058 692366659 23459012 82069431 452944546 303840094 229820115 924445773 905711996 382005863 848232521 494807956 96501463 753410760 65089598 919365911 83594821 726409954 590512398 328491866 651818482 867634070 376546023 165108158 827213383 92739861 248358511 439683638 417957737 530805531 701197670 852649301 86149162 409656932 859323303 876683544 399243443 54445385 928108479 411148370 424371349 752325067 359728603 946116020 632728357 836690533 510296764 153662694 656369295 321977668 521185934 203478864 991585176 712856553 897606755 707302469 286300525 334388878 521758534 338538600 958374043 155204954 6073620 995122336 819665398 289816582 611605923 484335737 106403634 107339990 589193693 346782284 227250357 657839300 813434878 496675620 428746977 80480277 196187815 547782028 995260551 640829605 268425810 315775282 30058075 639357792 543806709 677870925 126333073 686586319 744681037 43629284 576690371 741393212 941906821 846726479 336385523 327795884 590083095 452010012 168382816 76004190 18575408 587399448 963624936 616080391 598084241 535117150 475301559 139695574 202452809 717476624 240222575 188041114 191392412 634046380 880623728 691357556 181928448 359505620 186156759 853062827 128366243 638199267 472554769 941106396 28358390 986350416 972315040 954706741 66627273 200718811 458482979 120005815 378272733 850928216 771706974 705948603 157229251 735751171 315066054 291719646 746573940 250178063 72027914 42681986 170933749 199992960 531847958 147976404 195106713 688869093 70515391 576160444 561301681 934816259 801111507 310455326 127799171 7723304 285395558 562162089 588681935 492090398 497810577 767378691 444314210 880694325 698056536 957912479 759598146 592810859 109354030 239285415 429413452 961266795 684354693 276089828 760906914 157658817 36384742 734223755 468465078 762152597 231843055 417266868 472983778 930222759 898517791 559846606 981913542 373447696 587738781 41158992 989867881 27421525 621627624 953036719 379559866 32253302 870803895 534890474 519465826 55654637 743111316 874120890 546626149 934079974 394338688 202204949 730967352 190919721 777373439 836733077 740764351 61139791 155271426 710799603 967795279 163719455 171093437 287977114 953823465 431258815 993219275 789884529 585382489 951217029 690190745 97776505 329682260 429343647 692938861 676930441 283489540 929202921 152267506 560093058 112687629 481486277 59024388 801311280 125728958 808143481 377104856 65209975 438857557 197858167 255884354 4164387 612849583 319225985 459003800 609175295 816663056 128562752 301547738 673609663 179795008 382899486 125128303 722359023 458503016 115522485 403622620 226247333 448896877 319756879 895958692 811729824 163643007 504014827 265768877 666029710 549885775 640675254 511313596 895792594 571052293 965043004 484913033 78607767 899963745 640866243 744364113 266469928 437118362 450003418 300358868 886721738 395284894 887628283 306259341 77523774 282251800 825000598 861313894 813320777 522744004 844903703 346583981 914729953 66249672 507995525 600895641