800000006 357142860 509090913 109890111 279411767 410526319 893280639 270769233 369458131 463709681 63865547 56899005 21951220 587737848 953746538 745306128 309143689 661038966 104617184 498677952 479807696 464442497 620925558 466864128 611073142 986708868 993241265 963885096 248723189 306736744 294064952 58068589 839207927 904779693 738670434 169808175 820164355 944227893 395242846 458338982 901677426 213336616 766059900 96173270 814297988 262898255 956170597 594992919 500272088 284942491 53037286 990244303 524689445 602573699 381574204 209745912 742572932 366103899 362814641 801712106 424089310 301968372 234665199 413706536 856935674 630050256 482563531 127066068 486106003 767861939 377439690 494651845 987577136 494795007 215547154 850503139 172931776 157518934 612214765 916840993 776446978 699817166 354199206 133017959 953489793 346242949 345223931 371485320 237529825 654167576 368626413 600732415 979613632 167371723 476962066 181434198 440740571 843289058 431505469 38723021 329551340 721857952 366829170 93384344 863514761 248393419 845124326 130495518 985136044 813780809 354240775 560321673 510919445 876771313 547150643 811510444 133241052 221047636 6380231 528963442 545356018 773101534 434005977 636420988 784440437 183141232 63428705 158778011 821138002 894905795 192353661 342581930 716184544 392010420 87810606 496547204 86015187 891079710 428532280 228962864 830610439 627809762 38018670 235374253 530136674 229219302 516102677 360487734 122872257 842493580 112872151 89295100 621220414 781094070 359871707 67350180 657523207 368757190 577982377 536253142 941194520 528983072 871133470 66485453 718163827 70044089 565158852 890877790 838559479 269126103 627275136 522266122 249210101 165194928 822057567 272982133 269646915 512051894 623059367 114541202 403926069 368713223 115248310 774867646 591025927 853552268 234717422 4896964 705945697 835278563 899487963 387015529 224986648 74731550 716095615 974205066 4865321 617663983 746735088 214387982 644343500 549846098 101623247 429308525 16702099 62264840 17429408 100258148 399228381 384892378 173913909 431307612 657751565 737150204 239667723 917212286 333392838 362679206 298273614 534171885 303279285 549228384 74751430 296722680 653492178 701195535 482952134 744240392 129704325 328409027 295909442 802029169 122836765 96752555 461740350 166920282 134272028 9993359 384064066 557201644 804107455 233875480 615943636 505116895 765758663 543312735 169974571 997329838 6932595 420595238 612549410 139758038 762424793 521817300 648128926 163386420 700601256 822208187 149294958 458900816 462361891 569237422 771041309 589122077 333127371 191608262 550730898 603957898 686637952 305017830 861135654 305743180 885558962 974194583 561933654 605964514 736373401 190751513 968490169 493830163 565321522 626333791 125839498 236050750 147651557 63670575 549448456 468296203 691551818 479144507 882936914 93988879 801150558 166836629 979773052 940819764 767870689 131379690 770326352 718538904 99980444 753779955 670276600 46493514 248532096 697161381 844941170 192663594 652662304 668131093 496096375 194052608 202224887 316547444 440523209 585631417 902497207 490499248 459997696 757790855 17066197 607796974 209854865 186096475 194787491 626520194 894636526 969971486 699078533 766360964 902617723 704624902 365110892 895949608 850898587 905244882 584843677 282180678 425901972 929379323 126596800 894862077 212618536 196773404 334142521 391645076 788873089 140938825 962534300 473465434 43792549 989915111 520455964 865344223 663285927 377202909 951047426 39920464 30215912 866827634 316574560 387368773 39292292 129027835 983448563 671747875 56838881 815057324 169297479 301170767 138390321 664274520 64288901 767206554 248407806 805479050 329111558 701181987 630806481 84916449 348883870 176637131 475371892 966910230 816468441 505486303 721621783 402421988 949772673 845579905 581120016 909422685 244202703 651261685 799022866 725032693 463331968 594265408 575707919 274380337 748484311 789903823 488515062 18263160 936218815 739988440 17166877 692896100 482980526 801911133 633315184 948506151 915206266 239685650 528805574 856189598 747670134 152635320 889879046 657911179 976232058 626848991 134642573 759298613 614621362 618302878 894372960 856313130 229242662 272294741 408040678 590666150 11633655 582005193 409859272 8371871 668147331 508578829 89561804 932483650 580787783 191288895 241689500 972574860 155323610 659133018 339569421 336056168 217455288 758480465 93638639 248641476 850886033 153652351 735688869 200477 667445258 117587739 624088683 341513053 464595901 331887912 965262822 950400709 388337271 177308283 605126781 801463991 279636995 653951254 887628517 564754203 319263366 353737162 327821195 652608558 530755500 311199327 459262685 812734074 848007751 955417388 992478916 312546922 453338189 808517756 375132898 561350106 828540061 554848451 476474028 229536705 163237040 482228967 313423382 648088673 80378676 521469072 491389457 10755369 894640213 693919979 422853164 789800598 77388542 873668625 546107305 502514238 227320668 921004214 766927287 857452037 775030556 346910167 536801609 188519546 383519430 93022757 230324401 403222436 636230527 649315283 102002458 791023237 576724750 491416619 771043161 292669695 913522286 299026562 687513919 173226867 682103378 612363357 452920407 215285913 152878521 380956690 147252460 201010019 276421374 289743565 36469779 579944254 331335426 72618641 44479107 656758768 546319633 317904039 443552026 83569869 916720229 544617875 572484307 954903621 823454134 181660672 295293259 875016364 577837145 348161438 361067821 415573261 882882952 28866808 821187197 948852599 90213953 940542784 272999924 675817330 363362299 998019164 588773764 449839364 153801563 283561537 704504598 433031022 861700540 286081798 955364615 367519180 278437181 560777047 997451081 638380622 488783707 511591955 700867306 807352168 252495444 480568854 383027605 783039749 672221093 495131866 577474451 947285428 904820934 90061512 604743881 358640983 755002321 324250134 814578092 54382212 625327664 323567433 527426543 791341450 281556576 438111966 900117969 723744323 978740920 454804121 775597266 201154804 810731921 952825424 115808128 985056426 681626881 129402241 94554274 579528064 314320870 409618056 448742735 101304651 932605007 116678885 833030246 778134442 704502561 177059476 237800364 258978346 260840783 933178232 828185354 393261117 520583295 544551080 759536603 91325956 311203663 847336597 495680973 220743432 801214505 425478276 81986036 402334152 618961461 863136377 495879131 389760243 362333431 942653411 699950284 45463033 329872567 475356682 371720145 528063196 617132272 674006686 527544414 267302264 199008433 578953697 726655604 829644059 480426316 233168087 582042232 122446268 731270490 918603260 432383017 722824703 987122843 773241800 208675981 355802351 362558467 519677887 747993174 879468200 188832109 453383255 117394767 25232650 413588410 76061689 148817519 737764316 381618095 998623913 797289761 64678226 220203182 922889052 727198149 272641472 120681284 258499786 790881222 116894505 784967289 457180097 821500433 284540351 198772528 468121342 621253537 116128528 989847736 936429032 634078038 4937235 432491931 984366205 682736743 449692555 603706588 910279118 758510169 743041120 691106527 938423358 467294169 568459351 150392757 748025040 952136466 845768104 344854097 293737139 705550614 168530881 381089550 609215694 163175117 839273984 127380 655476592 292174545 956178855 317201648 398560187 984683351 425857811 226098011 404502987 950385652 84825644 665402558 757864463 253409680 218661019 390640575 24391702 35318644 245079047 159776417 11392034 633226249 128693162 857789455 373492497 63713904 902366695 295289675 397919542 421405406 830632138 756113878 85602049 378612273 574011886 561813855 996694240 738078547 523275655 651845207 683981476 514871817 857969905 428404847 675567574 615477948 994294989 88831417 118219999 384263880 184465883 70588521 536336437 65776671 387941116 436784014 193590687 488878093 821891032 960303262 62397839 592287904 114646265 769571063 77976892 670816908 252652230 95759829 79548486 799329018 253139886 407536027 507730901 483915611 570208376 341805029 900518556 613543251 157378059 12641475 89205249 441461274 855473973 192399202 651584238 751113488 318794335 95216341 63092985 314304852 794582295 456163566 816765646 873954434 50699668 246791028 261349098 86314603 924429560 319063778 429610249 769913284 390971391 830888209 43402361 627695004 319427538 731317993 636989090 873839585 438551883 659484049 140590004 165188082 333336805 749536777 252238437 312163612 450467329 171014329 517174662 725674232 728881769 574391225 80304507 48840749 510325172 875955410 914446310 599856476 723351648 469340437 598704917 311007739 783270200 570161909 422092655 76501509 383004666 635339510 577062465 64207915 33477445 899585815 821476288 77354329 611441358 755476341 867596886 651191136 200937725 937284129 225134903 320322156 281543519 425544074 370367028 659420680 356253545 413233450 899979259 864524867 977397642 853023438 282428426 48368200 995598539 570955896 368170291 291046432 791736883 559426681 609588967 393179491 820169573 431639998 637941814 513423524 292793284 844730766 682641919 461559722 547771115 4293875 108275575 269039500 515638730 901183245 377976650 479199877 220733636 508269953 738591152 182816447 49209576 85346617 977575428 76214207 334573239 90973672 75026455 380643264 262028394 416214198 868594597 809913133 838424933 188056220 421718090 554084710 613669308 935901184 140521510 341840747 954967924 250515872 136096396 174490945 876840492 644401977 656907208 501554103 404942738 387303563 548036170 963178055 286264811 956593580 563735156 698587416 379928074 134835666 617882459 260305443 70988021 463819028 682790484 999255967 962163208 179714645 514146851 848024736 682843827 689869852 205666338 959143794 470076572 162812607 213120668 713921546 752441619 635622686 183135049 758270577 968219907 971397308 789326962 441825587 30723172 470139236 173185841 243982650 732854915 168196493 496510785 325956734 30129421 146109059 740640347 267695736 669432864 27859916 127987278 617602892 884312920 679341467 811404003 175845059 501283491 598255805 64028811 642061634 627250095 418065944 328042683 853806779 424576851 637951302 127327063 513154781 445554901 514605739 34513923 436484933 885716900 331347509 311099920 256057735 892622995 737460944 931367692 1016874 701937376 174803408 818702864 479234208 142621473 703611671 748251922 635820741 947677577 657224647 626580116 726167390 916842117 608996425 980832232 587998056 207424889 674789146 771673117 314621188 344725065 599640644 828602034 974369336 111605129 734297342 411013064 498157508 864698239 196934204 301314712 133712491 887342881 51065980 153682527 753882122 658062301 52408288 884617220 693619271 521347912 286837104 309675801 153302924 163660702 467427586 319442012 307865088 218416255 125955161 804359203 455631798 748916169 961932107 369805926 392154959 147860932 488271355 237591779 322868439 582862265 932506680 312575382 306310307 250856682 416214290 749852153 304827322 768146276 784570841 289297774 686128822 251445753 357922775 782558272 895652729 125149676 379656354 620597980 630617389 641621394 71725834 941275994 309021101 486583303 765076332 577584532 179132974 329450374 902719006 452038843 239462595 196697697 933000138 286559486 721266269 331094895 983753722 64733451 718532237 236375040 525550868 722900479 285571898 108979669 195979310 528636473 460282729 824030775 794391481 415199944 103575533 239982880 355488398 893088502 305669523 922538436 426871993 808185209 919838443 598199551 15777791 736445204 216803665 977101341 76920451 871268384 528527908 587256037 669369831 453736176 360230719 790336902 422191877 97430452 757868875 26018215 54251486 51307311 865771888 124703585 817595545 538044507 68142491 56246843 193559034 717114360 73587322 467531608 71488562 331235009 640565028 587245293 526944942 797114390 807882578 774092395 930811521 178664095 499673416 140315242 719106471 844571127 670051942 513758393 642339647 548393637 148259031 449780600 299342417 643627800 838976572 443384693 251018351 931480822 292395975 600672838 218384035 777338621 346624841 695933170 913457987 956933396 609528389 204589184 392982079 945358299 563742211 754502937 381420733 134643159 294033808 720196896 287338590 184077328 445212575 831292081 162735579 854202547 380409809 33598386 580601486 146831197 507928712 512485084 842850108 291721345 852959882 501526179 919267171 781523925 554280753 923381953 525248832 66201480 379789235 891150456 300840763 23056470 231995823 288502598 231313692 571972396 625685143 893468192 367716286 982897977 627420728 864479490 771025235 319305857 475894263 870390396 942319509 738784976 325881082 738477423 75739195 734504169 548941919 417287171 646485544 972343812 903315527 954498188 354611193 648787107 92690954 487092875 728371296 838276945 63548969 466479479 992579090 396571730 935492548 697363696 18517583 702258496 935871633 436763247 55040952 485642787 145986373 801956579 812131684 562982340 330791135 638312265 820846070 704158955 638156773 259494282 176574921 166779031 82725007 133694721 226284118 945422326 55903580 162528471 804811211 398559159 80393099 746350792 939669579 591691294 733422636 52121155 203904096 311330334 965954899 852114979 899262663 173163139 901775307 944974860 972569400 271217375 230713750 775569412 825467819 916579782 899488130 361525630 483738385 663016662 897936209 971774485 626049933 555710263 447393145 92792144 355131996 650497643 175897848 751393656 572441530 685704137 994749541 487019836 409329463 705757316 962385245 256625209 719869065 57427873 848921418 729879258 426060534 861261740 882541381 82269637 745708579 236635035 535103238 222095296 382631400 685477785 611303695 381334881 789762267 141054983 130420160 198965911 15247175 205126307 155425033 296460194 318653531 476116605 94718747 697747895 123492896 695520194 489842247 931136107 257144 890487458 198260653 665533756 6784821 240611286 593350665 616540210 62472630 19926244 10548327 467655146 561060574 183024429 355170754 743130059 846922990 149326974 248130931 89903151 445546323 122778774 122975478 410451683 265460237 395019527 176831724 471327249 868464785 511095668 236319391 782903733 645033668 371099665 382713143 747395818 289058667 270343162 257974521 654162723 186160300 842209067 165730384 949416639 73367273 417437942 128509983 840719407 306897207 539458150 554552865 7709223 260397694 848223150 150012862 772811472 682286311 349580692 609815398 369577223 800324065 88354187 992173606 535990133 685184907 784858705 85161661 42781372 803761016 765902638 121597084 566780509 459297712 441179279 351103262 55985623 260961308 545828498 386746586 286517975 935382274 481972169 929220224 691256195 742331139 390211014 407739801 885760046 645888183 571523349 455369614 274989941 968742288 538813193 638497391 594945524 329855368 976623794 910616155 301681001 543189191 404204209 238661305 465073459 726273043 937852451 224395934 500028743 465897499 835225760 934214332 297821992 776154025 429680768 445717061 48329411 449023301 282485930 546103647 237940744 765140374 98067455 715639027 115610202 10524391 909071913 72569309 438934085 620025374 68139347 11416149 302652830 441811665 869654604 675592776 701063276 170527145 629496642 269213661 459397752 911791197 923872600 965688667 741483830 441832840 114436128 65649884 258952077 190171373 325173351 62288099 174377612 942186951 321277295 482192432 885076937 266033275 948375412 699024484 896362217 745488673 743968854 60599712 803546687 808872045 602200299 277921125 488482716 994120076 601599655 586914085 95941221 508807191 378918287 28819697 732421330 772177622 197087344 970413601 727698174 219401190 470397546 132370705 844405260 520418099 473492012 398007484 10187861 163759193 991334951 901206389 228518702 307850634 762501848 529894058 987856101 392746895 348104045 94780069 795305309 134569859 871450073 972294967 878810115 828988530 402693867 463263824 851720175 577453414 73807734 104776024 703036050 23262135 437437810 413352968 774270439 244222975 924836556 744823501 671607900 884409513 292227677 213703505 445535479 781064378 518586867 418231426 169101300 988234024 739143125 74918783 301199158 262621261 659364149 711282139 284744600 549662911 281339809 144290343 368330791 845765442 597880385 664029629 304317508 582971039 488193496 687173552 155634707 421569173 880650465 882087275 609773139 497774289 657576705 206734378 828755171 78841833 278264265 476967089 243465025 354546010 695565611 46870503 581215451 966719234 436250668 756302146 714028142 448766709 683524025 419114950 737689920 61098359 562863150 7172888 230939911 980434813 803750506 198932043 900449412 70360880 109470467 568862175 300035690 790960347 258585641 917532036 150054626 856938672 633684902 267263261 249884950 787854504 126975093 587947582 778397101 35296537 247670606 68063442 32208204 604797173 810426215 710785648 557513196 291884773 289432947 852781546 89271287 629378047 908542816 492016178 376690682 509601116 82190403 106516466 929986030 633088981 932389187 764448878 18413449 795339511 665662351 331236688 293785144 741969821 91867307 802929617 136239823 372628796 984054642 863125799 414052784 669496456 352971724 249162386 937120559 661563918 926938723 456521682 198245747 276053386 541176210 122003762 396172644 845318265 689291008 899367060 710660717 849395859 827328900 661314907 315565185 856402103 66598756 23123804 856943914 170819164 984709106 125233979 926244582 731271296 950063556 961085682 494459619 935708656 650149363 96740372 59975848 15465305 261143028 437924788 774928834 777794691 122610562 518436606 815750501 985425657 733306622 807247314 395480643 509930819 896886426 588906724 960630271 212793123 236326958 175241856 288514430 514571519 278991070 908881263 186906677 928628114 158195691 336264466 875072585 575898469 166233025 216115549 653384964 979308745 549344748 233191452 471867340 53888699 232865672 657642381 170282413 174262527 586746292 466277584 300106393 771896366 980098735 951216545 294070109 711234597 277090578 538301356 187950886 92559920 911695399 280456229 975678485 251949876 508545530 251247434 894429410 791375918 46694924 371251209 801850972 955714082 623827566 549488310 600372437 450550815 517476979 836153119 648951022 172671053 383745104 754536310 414472198 986285721 851035731 655267421 674505078 447669283 895836562 277609270 200559467 325449874 296755717 175313196 817535142 84828753 473852335 245540018 860071151 692287900 388486966 904686046 901171028 35881585 654717830 476203069 106932453 272725845 969639780 882337204 577492071 681220825 841424073 970291855 505752423 99218386 489187394 44095804 738506868 163265678 9846453 745393545 798606011 997790317 875356767 507589377 654719919 325111168 652879773 293340432 220121913 845434334 423450569 180277370 148482636 432006097 80074603 89652902 129789616 991588014 679652668 161931186 867208238 944468564 991970580 252189550 421090740 484125758 189615859 384585846 916502876 570170727 474971046 991382326 276106415 85433402 396917311 524246306 861946824 642722828 14899098 580296751 692709881 167585063 605282857 188479812 591331214 366261151 512003470 992459500 642235302 808902275 147128436 97240671 87134736 341342902 59201371 756194387 808860927 330152186 416834294 583647355 424061960 33819578 290404703 238116750 32520194 733821227 265528043 848832707 44178346 595624618 133350472 762310625 259662695 126775432 538108066 891044784 355133392 378390115 907146100 534652045 539858035 808415602 364901626 701874098 539392726 349012797 789790074 962235478 537226311 231123119 498025728 185091070 273361794 668780070 717243450 467098383 210589139 67539488 636347047 54363661 342160520 872753915 303810748 348851215 119469423 252083702 457622423 888122603 944482061 267285207 939281387 370710284 67105991 476657198 675243444 283725585 556560413 432283320 994388599 762887129 722437794 450006135 652013396 261599074 821865726 447709693 31146371 194612826 422907799 162981273 338974939 345409997 801078971