8000
1 1 1 3 2 4 1 8 18 9 35 71 42 104 104 53 275 466 1169 1842 3709 748 5488 7535 10279 10853 14301 42686 98526 94332 89970 73054 238200 219945 212927 311069 124878 79021 45527 251364 32314 16356 88100 399752 307823 19455 143762 132520 117177 492053 16187 1700 244014 34568 14197 577248 9679 27124 349310 254513 40868 176868 164810 207844 156520 273001 64172 88129 264958 316431 636069 82375 23562 234327 167669 38426 171938 56796 49500 508592 347362 55420 9645 261319 63033 40724 124889 224763 296850 352026 72240 215319 74996 165802 203500 105013 182260 296787 269673 1162 131155 651061 57588 8355 471255 570158 337701 114198 236540 94214 74560 136414 107805 145736 253647 13114 66721 21374 574912 183662 600647 137771 23005 50821 239387 620942 304829 614170 110996 617824 190829 53862 583986 29679 5611 33066 479138 363363 36240 99462 23404 151302 9019 24727 89751 67240 75198 264245 41141 918199 5207 256797 195902 17690 280694 534619 341980 194684 367815 486073 76110 176536 100995 38242 17468 774693 751604 192983 9329 82883 258149 63781 3165 74665 239377 58340 13631 557591 73567 210239 110949 261436 394046 50728 1917 33025 222859 35564 217472 78008 69506 503148 139332 17012 3504 199781 662247 530274 187316 172485 54195 5883 214612 328602 70644 63695 105130 251566 13225 77718 415820 40338 103459 26202 40232 28687 40048 231064 73294 158741 416666 174219 38556 130664 9546 135649 62989 105203 84259 42042 644899 24745 681178 57521 33317 127118 493569 21676 62682 398785 23824 292356 576975 6232 113714 291462 93554 476669 274090 453699 15820 30646 60341 80139 399205 64366 273517 21268 8203 59917 347608 190037 445042 37884 194952 105086 30656 52190 17181 15616 189400 148430 33057 42430 54682 292916 29125 87889 69388 157045 411895 366641 18247 201684 59558 61479 183661 104261 235498 98213 227924 151978 792 24788 64251 83166 857798 215836 376645 240155 35947 413300 71575 653230 124012 347620 18626 85934 72884 38693 257802 69603 232319 381252 222114 142155 556249 58366 16577 38013 59488 440715 196021 554 65427 199203 291387 340797 529408 294588 23955 98665 4182 3560 18855 606315 451061 116344 456478 277523 186332 778527 466823 7353 481597 59198 22778 336029 126446 180045 505454 117467 40479 202341 962119 387057 22260 51698 557319 797574 197519 81064 268354 52619 252330 197728 388569 193580 19809 127602 146866 3240 308624 166993 163978 65541 376171 27367 138780 360136 577000 39208 87558 154139 64793 68474 48928 45896 601242 305422 113581 83619 45653 157096 258065 50504 33829 207047 38223 32248 73369 235345 21379 206324 168483 145919 191960 275370 271147 110171 2875 355951 42526 63085 414449 56401 97480 31618 127390 22927 84306 59092 349240 144208 276449 34807 161618 143134 370390 112535 69918 222285 73048 411104 204135 115141 1177333 385626 208566 13140 485544 118397 172306 134025 133198 65744 186029 146039 177284 145532 43793 528329 245551 175489 53884 72154 133322 112436 119471 95016 22630 39224 223076 18479 229262 326290 12970 18078 407253 18175 88650 256984 231374 448396 1021669 192338 105291 130918 183362 20344 64719 297600 508317 770956 39271 6028 181676 90896 68343 329175 68862 398747 49775 173833 116340 11211 220809 108162 121873 6856 36714 43829 36465 90827 324432 95471 118856 264060 211883 1490863 9100 213864 241050 326783 216323 11806 164900 67060 100570 20153 8891 143008 206509 139807 38435 603898 680226 88964 693607 421474 78851 523391 380435 78165 60207 612256 75503 305842 180681 107330 42650 411946 471494 268099 48708 27212 45293 65672 336249 100563 14748 266861 584970 16528 5043 297275 91010 161700 199424 203153 439272 261767 55261 14799 123090 69112 572444 487487 93423 74713 360376 58925 293086 127153 18624 32336 51016 348812 367861 58314 10658 89652 117809 18036 29710 130998 149909 161281 101825 115096 18792 141543 29391 111732 301447 167424 125615 205989 477046 9474 231145 255763 29224 432643 207433 257683 575730 595431 76090 209230 235084 71863 230142 153053 34639 35142 13162 92512 195945 12255 13299 49055 245852 41487 46981 272372 372689 24004 110427 21655 175080 131911 171604 18793 89157 29414 41640 334332 375123 14488 380891 109769 248915 176249 101920 270521 75948 179002 719719 225054 145911 44475 218224 137777 270655 116706 319497 137180 80353 754901 303713 32239 1288 71782 483162 318743 369843 95028 248276 129684 60558 192164 30964 40336 227438 56017 26995 198678 162068 84952 28860 142855 400725 31418 20102 79893 130661 126131 27668 62996 296374 58365 49206 28848 172404 47428 92746 188168 503801 993693 158690 20718 41851 31379 240560 106985 157993 168763 103286 177726 11422 8504 173382 202926 172897 25632 206509 449163 152391 8055 234994 330203 532921 69107 169281 194907 124589 30181 175589 365067 32201 24798 543710 4384 137867 246855 128377 5890 70450 63228 478597 284767 93806 6075 43987 25467 342560 19202 177073 105350 28053 196610 373685 222527 144399 295217 126719 114465 28965 3204 238543 164170 38047 19197 260625 31895 89620 231175 37874 153981 258230 135610 34711 27692 350792 43140 108484 68607 314928 77091 79059 234119 202804 158308 710906 247620 600148 412791 60980 308379 118132 61651 720737 55915 18684 345152 127412 241944 81334 604612 42629 316943 732894 46836 214444 61730 372442 412 34053 298187 455620 28018 234262 509873 18687 37443 292336 600665 240273 20855 298167 36844 396751 98046 249211 13816 308385 71187 139033 55985 142254 125025 202855 541013 38806 52539 244277 64024 358872 348130 116591 56585 65560 16252 133010 159340 228962 37859 102017 341230 414726 597032 687285 917251 279031 172085 6484 501020 52347 500814 254782 353005 23576 6243 659463 281520 29628 377948 299740 107980 110163 230650 153886 282023 309319 75917 93923 368255 30215 23854 58125 46504 135131 341422 286897 548293 156773 170048 144928 376757 33653 107665 46106 366704 15008 189134 94046 32512 51813 37632 59063 17499 213403 26776 11896 86484 3103 368047 104810 166638 55369 81105 58753 84480 141506 254648 287082 408339 367918 44220 67576 192239 136380 59625 74540 478360 44048 145768 241008 125318 105245 94394 34610 153470 194422 183202 24266 93823 148526 54213 83666 52662 160827 187843 63420 17767 11059 28613 179705 156212 181513 43319 609554 39954 556292 390322 87079 288070 398958 638091 263235 68461 173778 9892 438831 40486 72147 114478 310694 57542 171742 7881 174102 170065 11675 14007 102742 323409 75115 316138 589592 77960 33822 25831 5483 100822 264885 152451 18416 3494 150304 584909 35676 67962 84365 127953 89663 183336 152387 321083 423263 400379 26688 68090 282084 47327 17735 46274 31245 32309 92309 108059 58719 99865 130197 220981 96395 131582 154071 589173 172242 47246 362636 148652 72582 827274 81448 468572 736299 6415 198154 17579 170697 231448 4883 494694 636650 106813 47968 70524 202034 60635 175987 194967 996635 20912 176890 264075 150073 26121 103285 493393 299204 344470 236862 209136 1107227 360021 53273 284647 367426 121639 18224 230058 62353 27056 310130 43970 56601 706687 229122 651363 274445 196061 91853 27290 60169 15498 159874 538174 62990 10638 90674 158822 112086 195697 51079 166031 824957 99777 53758 304612 263040 174214 302243 198655 192262 559 6062 451673 6394 622748 176572 103625 105265 145529 101103 425088 651984 48786 215273 191087 54809 147087 324173 629010 19286 36669 53057 32736 277019 1862 275777 647543 25668 85242 171446 366893 60148 125993 166194 23676 41183 355387 297159 618650 23975 24697 234039 195154 97680 103858 135669 101219 116587 137862 430402 119608 188752 55111 5050 245834 30926 175194 47574 22060 545447 40733 179915 9497 174371 476967 165411 15269 36627 781924 332751 202774 150675 60379 22863 63238 124760 245218 63642 13111 133287 104687 95679 506775 87036 192623 620675 104887 46815 340362 379530 370185 140790 25790 45879 331351 145236 182305 287444 380467 309362 113790 76359 264101 571494 224949 409538 237610 104260 144904 159626 954238 596949 284333 61414 273939 243383 226540 85973 83912 27716 94396 1030084 34405 262578 575790 31024 308228 270864 257212 254786 61608 242826 269958 48199 205817 406487 215128 195257 70203 114574 850032 428623 89833 133504 301801 9726 17433 473408 712564 119672 289252 60125 170794 47117 361869 306 285707 249706 132281 78266 226236 279506 215340 261075 825639 262640 12397 461033 7954 238308 57486 25552 224202 136741 36830 141891 654519 156382 187889 232752 222173 236657 234373 2367 318012 136410 109834 42662 23941 70232 218959 138059 301940 18040 416507 410707 24190 18293 71243 38585 251576 113430 239509 74059 533269 32970 109539 28627 255867 233584 241092 210238 234514 13739 263141 321474 30002 322534 118330 99057 22666 212173 487051 23492 29956 117863 128638 574463 156082 110895 212628 3948 234230 493554 366372 162826 31438 422866 199739 370448 340683 99433 132788 166250 51274 106431 1004603 217278 326097 86526 35411 508464 13088 254366 31750 325207 123492 39279 28419 296876 78389 232350 211606 198811 294487 220299 502675 97079 300071 110436 260471 3765 500318 427274 329825 72843 348200 20459 92967 350480 20270 297057 73446 202800 12826 76970 24928 10323 254670 569107 14186 221032 161399 10918 141092 182114 252201 55377 253203 90214 358321 264733 69459 568096 244671 230414 137244 96131 155987 77720 59170 290197 271392 70213 124810 170252 161259 390121 46361 91882 425297 284704 44064 94751 151592 274602 518503 31625 368288 561169 365134 41512 360447 151039 22527 18505 151449 210210 377950 92762 81541 4240 121805 230027 200732 254163 513060 3439 222966 84022 23176 164422 81822 92286 345957 195503 74470 113019 45329 51640 21378 253930 53632 67354 171302 7199 58240 136177 106741 632126 64584 5026 118115 80039 376884 138416 38596 119837 135165 75763 88176 221220 274161 38457 625978 224078 141233 91185 115400 39783 4592 69579 150679 34475 102314 69018 1883 82548 57235 183013 5896 195986 363636 108467 138593 2288 395239 356059 52159 417948 191655 85452 18222 113094 269180 137978 45160 94112 352100 74398 226329 89649 11238 188538 93940 75781 336016 126047 174202 91324 463094 13185 105558 114877 22944 19259 86163 1802668 379334 39836 18198 133152 97730 303392 194705 19457 69465 90204 72317 50114 121114 487755 3509 171605 184679 489872 157208 83850 286466 17408 795579 423918 199508 97558 600061 107898 415815 13429 147038 4296 339991 534553 118947 198075 100605 423540 43124 24724 557681 128487 47062 274297 123381 311759 44884 373653 25409 109883 161255 279160 57727 21235 65745 417450 26145 219158 31871 216966 465567 60523 207100 22449 30589 69182 39758 198451 78970 186613 265520 4868 25969 25810 490208 48957 847229 64016 132992 283413 282924 466260 14676 24927 23801 33376 96184 7026 19498 32572 157665 18480 78509 67868 287262 62506 593747 31287 430335 9337 214843 185624 66701 171765 128464 355109 31524 281657 417097 69698 90048 106542 91004 98496 220522 368485 151903 99562 149380 160247 82095 48309 120123 830255 59140 755 24879 33703 288390 75137 112645 196714 75784 296151 62993 154735 262263 33126 78605 57756 88615 532977 40496 50329 240106 268500 111425 92470 356585 402091 306063 399577 43686 76086 60861 472439 90664 213631 88476 305034 134116 46000 223893 70807 10686 232869 122424 876977 59209 329702 163118 16629 106706 77738 28279 20719 102853 130774 136132 31591 30650 5308 23324 212648 586850 1143681 430754 129164 93603 217199 191656 361057 606819 40641 27709 17264 554256 619421 100504 2042 194795 9767 110784 84802 25332 24683 510914 25497 13767 166844 47657 5035 30530 82358 49690 57795 235241 136468 270558 138737 52037 93527 187184 159470 129676 928891 905 9457 438609 12239 190363 53622 17109 75385 187069 18489 185336 1219459 158101 195240 361356 2561 437536 113544 100271 36381 24437 144240 181952 52483 44723 195305 69402 99591 449516 37702 377399 244452 270639 399979 148014 4291 3093 37750 225950 312030 238875 2976 294960 14362 10079 136434 291380 76211 240121 47987 76890 71229 45258 21912 121120 41263 58257 633275 382884 350899 106120 14642 369743 90263 240505 45268 11557 258650 983320 90629 41392 25821 42669 96540 411428 315473 229743 16660 23562 50248 54404 236528 9424 100659 24845 184102 175050 181956 401695 2078 13288 340925 189809 683531 216910 44401 108947 137247 267170 137757 9082 195486 50421 154016 528453 5617 84498 53615 608979 107700 89215 187066 244200 99366 171573 32356 144893 7899 88498 132014 95568 72482 144136 229063 77781 187366 4928 51779 28812 262422 2521 146700 231308 8865 87376 31455 242081 273554 70303 94793 189314 119406 51245 276499 7214 15531 46853 347194 49200 48876 64665 779230 253465 5453 81595 107384 257423 56425 614570 156397 310335 896639 26681 412105 393110 170864 71649 170244 58567 25939 584843 176853 21871 106555 783004 110394 95231 158084 144925 69961 30383 258011 59352 307038 113517 172091 564185 132972 151586 817 79056 155355 54379 525485 160434 282355 316978 129855 100176 7275 22169 391016 131105 104852 661102 72988 265171 273148 20766 116183 109482 127543 30638 567346 9112 466106 103756 42178 434232 418224 114050 195277 45717 50859 22504 387159 68863 92518 14742 337522 342097 273879 227187 22253 434087 94528 53747 27879 93389 83414 35350 541315 203599 131022 41454 238671 44851 47792 49924 261612 9645 63763 24984 67115 286192 340407 272478 372289 145216 137705 435188 202292 98992 169354 68551 96371 84942 21550 4857 509605 33425 174358 391052 127451 103180 219773 21330 208456 373541 210711 844382 50476 252173 311071 1336 52355 72876 554754 485395 155270 103425 8995 22472 9339 228795 435487 402661 85353 99567 108267 290427 275004 499380 8632 218997 104072 28196 15173 99696 367238 103629 54475 108962 200432 515813 49240 98699 226809 9257 153936 21731 221949 302130 99413 368842 212102 32281 228899 284300 160084 85783 7316 18634 474 40223 263782 88143 58561 27522 21051 150617 660464 38047 223286 142454 325431 132049 101893 152682 99955 15006 130145 121628 382587 52354 539840 5841 111999 57538 143517 434556 106108 122656 48523 293637 129334 384457 366568 9740 18176 23529 150508 689990 43595 1042018 632 634362 71254 117179 120844 48092 118661 42786 118823 151910 193981 182351 357006 121899 70197 110583 453959 175483 647746 315301 96241 193664 208759 301392 13654 109881 38740 306403 143006 113343 183129 72852 60253 63634 314157 513300 330188 30634 321262 58103 105316 171315 83179 6085 343965 67460 287553 84538 36638 735438 415174 474288 95856 135702 138981 310776 47022 178940 37591 46594 130231 310736 85402 269445 372394 4219 338375 91361 24906 163110 79931 23232 1019 294069 48528 42171 519947 369972 222234 52939 728678 51367 73148 30045 153362 117614 53887 277295 37493 72114 173011 137368 216221 2048 95227 62335 15367 460134 106911 93815 208047 68610 2211 79897 378975 92505 171419 51947 210363 175863 2829 124586 98219 400856 327638 29357 552675 200410 251836 21665 5412 25828 421072 145447 122715 831466 322651 137420 313525 314262 122066 100413 304176 6858 322501 973847 530018 309195 105542 10490 44346 76688 384641 10829 145307 25714 366699 49671 244297 3447 47766 270002 221404 195763 97197 223164 45892 338960 28173 140357 273225 1593 294814 44742 78420 32146 79063 323528 11529 448256 204194 446470 168434 9410 10397 142569 908356 49676 66069 9775 326500 61586 52653 174098 90222 297852 353942 18453 194541 115836 92738 619288 26429 177339 261493 240624 103919 58410 585829 19452 64490 233777 530311 595 22008 164562 225027 61074 69348 116650 94227 413542 395391 22705 60697 401059 241349 40631 28082 96393 69065 154461 123812 58064 93293 86808 1135451 524747 239061 154118 136188 213765 125577 32074 127911 90595 70400 184331 243120 692998 258374 68054 56183 100786 595556 137197 238073 253838 11287 1367355 70808 26576 66166 289679 43256 37251 194166 354663 309855 56609 1366 53614 40510 18529 11617 45154 172277 5720 33970 65224 142911 36 259334 491066 52003 154545 23768 116135 63231 28846 483765 369373 15112 41366 15766 161857 123141 30662 62205 46848 552422 337317 173393 16345 92276 64648 70806 91456 229530 127104 2671 113906 29410 250148 181766 203600 177663 104222 41627 223283 19625 228745 12936 32357 545700 302438 456623 17466 20419 121545 149379 88070 300853 200479 80939 523398 224832 35002 7143 35219 155714 6841 171427 87968 309820 51846 17805 2180 482518 178018 365456 87510 274294 32453 336738 67358 38659 52253 51454 208212 310279 108476 41316 214163 173549 90369 883 110837 30725 136744 26814 258066 143323 525436 48889 163940 135882 42511 66051 56496 22782 278548 35029 47852 393902 578230 44705 53594 276314 147749 156980 713148 842267 3727 156727 41168 522417 185021 37184 29830 353742 201234 167756 144 111839 532995 1624 536723 398924 1721 491695 275958 309959 149420 43384 61429 442372 604150 95470 304797 155669 502832 90042 418849 11587 735855 2586 247515 241589 140597 64656 70609 107493 54833 302110 81181 56836 7993 152480 273234 158162 359041 273775 214598 184393 75541 117906 44248 210991 12340 178370 55343 78579 117477 71314 44218 303287 258082 86477 6501 22145 187510 47501 21998 465562 808 441803 37443 181693 282876 2880 154554 77833 118035 25324 81646 39678 99726 353082 141058 72836 51110 319256 280380 198821 359219 58924 365206 232371 49683 509442 207691 632832 49003 100935 194948 41194 23549 39742 104571 297957 433814 326845 284107 145037 379111 159037 161955 149997 15970 58458 165397 192626 16967 114067 101017 74756 53654 90178 143050 116021 61009 172126 113115 6562 208240 105755 31596 108 211703 42494 357084 48042 253312 18436 76958 231719 226686 490800 778380 98495 177235 497899 366621 43592 56492 66869 147524 84847 6985 304591 846701 45323 54249 191890 426323 372527 334275 42337 133576 5726 27433 153794 342266 203496 106987 145443 221501 201872 456462 106606 163917 32823 22651 465090 98087 362793 4942 9463 80982 479257 396748 136310 413295 10268 35595 1126 213039 97914 354308 17319 221860 295373 70659 365228 303401 120295 226040 513893 193044 234902 496862 35931 115591 219943 56156 17579 248867 65833 12030 219600 63478 95685 200058 50298 24739 373528 86588 119536 140207 243516 311875 98053 159879 221786 1073008 12729 48878 206880 90703 804742 4406 52610 105997 182221 165833 40653 53688 182847 753953 63160 99752 43832 454138 120397 99267 408120 210004 28547 337371 406045 65969 285041 569754 142951 232247 54566 154081 67608 467118 151693 261882 182152 444842 328742 194200 250728 41145 17455 106160 250720 82885 74755 492170 654717 7229 461232 271731 180156 773139 97890 69223 158477 693736 465911 143776 5848 488361 22946 11175 107823 111832 225631 149477 122630 27251 424793 52401 129831 346866 324212 5216 4717 926922 20057 48401 4980 116406 36698 265654 12075 173929 6937 201325 5270 51241 226445 168529 164542 48159 238633 23822 40145 88185 328435 254858 40297 356528 20336 1349 408867 565119 214747 607731 79246 170877 157010 340429 6188 219288 65249 98738 219960 338766 203180 149244 141296 67608 133620 303753 474601 171591 327075 67065 41483 596986 86711 38441 119488 77115 524056 122232 13333 94180 274450 53210 91216 631854 44115 333079 67211 58414 60661 174776 13518 562374 92250 333838 352482 499075 4328 95563 133372 254330 956164 284166 222267 900275 93368 342518 673604 160129 260917 82988 51671 332859 313465 136941 684236 243205 116954 361553 12048 26701 1669 334560 533825 490594 16491 32512 281633 11887 161912 47481 225116 477912 37286 79113 624882 524324 66560 46816 319322 168088 213555 8877 58593 121958 66148 110335 168627 171745 41444 151540 1238 158124 162046 58801 3269 219089 44655 265216 427469 23152 247847 144443 58995 45671 229909 347604 75583 4678 358034 63738 134396 1212556 87490 69466 661523 561 32688 54167 165419 101722 57220 13289 117269 77790 117697 11356 261761 510412 645043 92137 47976 69409 231046 182286 3926 42865 212856 229397 54529 129483 191631 368930 217727 64968 199107 66957 44844 206610 148578 127912 278740 140087 16087 158568 39316 104567 97329 131414 148883 346441 647 91707 116974 108795 200008 65045 85833 286964 98694 57227 351062 143608 555444 106242 69209 519453 116308 239959 510378 70013 173100 59516 13566 309309 151183 370976 165800 321940 14620 228661 194619 106365 40337 76743 229844 8269 26688 749160 832055 274440 220581 272688 109879 64204 280739 329454 289448 56408 175459 24904 18858 419918 526540 82732 46198 84949 339610 127331 125335 20771 67720 38535 22402 525097 56292 83331 296112 73868 184884 273586 20447 369471 291400 125157 108797 4201 437295 188829 65594 6981 205195 217046 52929 473736 344406 123155 252604 228904 64647 47986 127472 107394 92987 172291 355360 169983 126978 131377 186853 147129 284737 46776 28102 241810 14395 53309 118698 113061 14980 417790 406483 26875 674081 228228 136527 39275 28285 657262 126570 164058 32883 20225 259710 240969 44233 163502 767319 241801 105982 504488 12961 106430 413031 360355 124435 19931 1963 89530 5603 5266 571217 21410 100054 228695 590912 37972 324115 412916 263349 51169 158218 152163 300068 229428 238730 230579 896201 39405 261071 74181 59772 179622 48987 567433 33930 80020 2403 417740 79479 280818 388687 242464 369792 521713 31131 256534 300634 165268 1029091 25623 479989 118786 296268 28004 195835 166594 47376 154325 143370 343047 45705 74904 104953 372804 188020 6731 243566 128503 11848 151511 58642 191302 23119 109478 257311 135223 244373 72045 55460 195756 141126 180264 101054 197881 114360 787477 74648 19642 162421 68245 117353 26438 39354 68987 53516 205706 214888 402619 162322 141181 163656 59868 256256 225911 215692 179295 443118 6295 379546 148834 130007 417025 9862 100793 149504 100057 41871 453383 79352 450674 290182 316815 30832 244628 1133807 132853 121797 99663 14518 180727 36247 35199 877005 212734 116468 504161 47293 311419 167593 55598 174019 1058432 271826 123476 40551 187787 83926 357871 88268 63127 98849 20151 359699 229303 706789 16186 70521 57794 80899 374249 379226 54213 114752 55257 538664 10566 193286 183480 564893 34192 35149 97940 43253 357264 45167 162782 292671 55009 18305 79802 460243 402033 225899 57765 9169 266586 5854 34653 21726 184917 124879 132846 428432 397310 46231 18706 124187 340701 315607 20808 95716 48798 249746 32246 153830 254553 92847 104211 216072 65151 221230 29385 60243 232397 1135860 130928 340859 25124 496455 375202 62289 489191 29382 169253 167690 186119 8793 521662 10941 194608 68410 262856 533106 117496 203079 130557 6434 80514 106779 206168 25773 36378 10243 203050 112925 59974 231124 2619 438233 9884 252850 375519 12070 61490 99208 31082 240120 83268 104026 8642 114666 897063 229781 277253 462005 54043 3589 55353 293010 6434 36496 23234 407045 2023 566027 355923 18480 19245 76558 33413 141904 175503 17375 250969 59310 157821 55532 33614 226660 217437 200873 315604 262216 1798 107976 180883 99377 212966 18132 232186 202632 16771 64671 113081 300187 22003 33828 126375 62916 362131 248889 403971 36185 41166 172954 505726 292084 82583 227258 185281 164850 108550 75070 113451 112985 206657 98373 1020910 371949 121086 141917 84800 12979 13034 49453 101617 68564 534259 67453 185774 304278 179104 55286 2506 267516 91106 232848 82031 79903 100363 92091 120397 254394 605953 195015 40689 104332 29131 465315 8352 34143 30435 304418 11209 312925 758063 80904 477919 594799 21690 274002 267384 534959 218436 112370 62463 332703 277898 517105 565684 181514 383757 38165 108429 187173 840069 186509 63167 202614 301684 355914 198353 73991 153126 39876 55998 235395 32292 94140 215802 165117 424216 263379 217349 5510 174718 550168 163910 239779 275050 161615 209315 174953 89243 11257 304796 114930 46257 229824 43112 2527 165084 119072 139097 128166 23335 123261 104536 270519 66810 142798 278750 231242 10728 146653 239183 373 11216 42350 52912 159012 205131 43 37700 294698 19470 155915 121845 357925 409910 121283 273042 101033 24177 85573 108495 197066 1144 89655 268304 131804 311752 140755 590635 12418 198175 657545 80236 88650 70824 178706 24103 5131 18407 11944 91855 32200 193911 7125 160417 401940 87295 437479 130214 164241 34065 199875 13984 221439 113816 116208 297542 514565 91394 123755 129344 37957 74090 213591 38225 58725 144952 136189 298416 144666 37198 331621 174984 25375 371490 84623 252116 221908 290 58122 145543 956 52709 14504 84874 27647 74476 203662 593147 784790 195120 245357 113238 113825 62078 58951 11039 126305 168485 135115 146040 1188261 25241 302149 88079 83962 11891 181460 18936 12921 367112 474894 26470 374751 93016 230145 175762 163419 325452 90242 103273 71844 440449 13556 28870 213990 80570 59513 164757 232693 79690 162068 938 234386 45447 263936 46210 51900 347082 115439 234056 212739 52494 30793 234613 26860 118693 213541 33675 4727 243726 306018 66161 659232 249603 64230 429781 320664 3065 44530 208751 3319 171478 22702 94 30855 310164 27853 320590 306665 91387 170268 240053 59950 19898 113278 848574 9633 5780 337914 49758 165105 60299 336797 117752 63053 61243 142803 203547 55698 29481 60470 57386 193572 49719 39040 123931 68504 5538 401548 367630 185841 295519 78364 46743 81397 113940 58010 209470 298 31219 107913 83648 206242 180935 72539 330743 64615 137453 241132 121122 209917 1183912 50773 69859 46240 376032 200981 18933 73646 58208 43362 438269 29975 17381 158127 328262 209566 684324 2612 183446 400598 160341 407129 117764 10306 209526 39145 121015 172003 226706 29550 217901 105347 335887 11986 34945 12493 14251 108214 50693 22562 105264 32949 133659 124582 217488 505691 330530 10924 93939 403061 172983 26319 66208 10975 167774 291667 137421 165878 46288 488657 10953 53912 147607 11364 20388 266073 237056 108704 107234 261513 102716 96971 116649 152113 120036 206534 199610 15743 59502 412287 53293 109177 274869 140715 67146 89913 124837 70071 190831 272502 247632 94065 768052 41406 113999 3621 448723 27994 53964 296388 179362 10178 203509 142883 207301 59755 77660 17744 135912 139630 111815 187959 20785 352952 6032 58518 13358 188894 41383 59707 17039 476058 107818 120467 93262 183366 375032 47894 101518 137626 93664 91122 146157 376 750 30743 205133 1121573 23832 300447 84627 40714 116807 267095 505268 305186 245453 344782 275468 127506 71250 177246 112494 50253 3325 374148 184550 271516 111705 87 110722 143932 334529 186158 22210 113633 170334 753610 85179 274547 94566 567966 287856 72288 76573 86863 4173 59997 280100 242584 794550 264897 60697 71617 98711 79690 113768 60975 680027 76774 97532 425118 395309 340968 308469 247552 32390 89020 447537 345723 256592 173182 185401 90333 391187 140474 70530 146801 9989 227017 26880 42868 350446 575685 96857 5919 642527 104116 369242 63790 743414 396097 314443 432208 70151 125444 221480 664091 162577 126856 203202 16698 45444 258697 464797 246500 615837 300180 353206 16684 19074 19966 419875 403154 666 66767 13835 85436 90736 74576 58618 76304 90750 43816 31897 791727 115048 125771 16483 58949 339668 586626 254189 73042 70152 308015 39040 184707 354166 16253 123615 336766 183570 24898 21840 176632 473306 154326 19368 56621 41086 41393 80319 99861 25709 67571 204872 75424 335937 96982 17551 207875 190657 14993 20287 55432 408105 79215 242355 44919 141467 281627 386612 33205 431734 103068 111747 48602 29593 414347 571099 18041 472976 254639 165075 111324 6314 59715 70548 147539 109337 399007 354587 19919 173276 118390 122218 26077 887947 88213 122597 39220 68987 372603 64883 194251 262901 582631 245299 58643 135093 66422 7039 17398 195280 310187 61749 168621 360700 263525 261155 273701 99964 20861 292073 160698 101962 25175 205768 575417 198747 108044 118161 238525 166290 285604 43079 290105 359028 697435 27286 23028 60807 67178 22954 194158 591833 12722 103581 128921 75836 135691 44617 126775 373965 219612 46842 3374 192111 274667 98219 2609 89038 56248 208310 7565 115324 198144 28811 447393 186532 325804 217941 3821 95659 20809 666530 4110 71479 121206 107108 211117 72421 185164 647418 19261 105874 143255 242259 7933 147208 340631 427676 90685 574273 371 13073 202814 50394 211010 51907 110070 30659 218814 23891 31984 192153 56039 27996 293414 53507 254648 58604 642018 232849 70058 69724 1106482 66188 14501 132149 607371 38036 193980 79582 29748 481213 78777 93519 96854 600393 156764 117184 117896 74509 407245 551778 33054 153564 357045 50979 279854 33654 50997 170202 286490 31907 235490 84183 222150 138124 208682 213856 35340 101877 152672 442789 34626 111109 35442 201668 38982 518300 597397 59288 224311 112080 14887 3515 1043717 79916 129077 623053 16721 386364 12337 141780 234702 59023 439899 161001 1089474 92374 112962 128754 1435 134496 296380 238835 71350 348611 412811 238534 63160 103872 239321 262390 118173 40811 113353 149036 182710 445799 388315 528465 11519 223995 48945 274197 197554 7849 737920 458941 9308 330111 39496 197351 143010 29688 233658 116327 105484 31730 61345 121499 41753 131644 195862 418582 117014 212032 153423 21323 351807 199171 75170 164779 140309 187387 266028 38146 93561 92558 343587 71115 33761 103467 36244 246855 255 52442 118540 8118 261825 576949 62416 109135 36335 49040 98182 73787 34540 258463 225997 28076 397821 720586 89759 46917 51977 148469 52832 123836 352947 73069 340749 282635 41992 109916 196327 149226 147546 62488 8717 256969 97582 23236 110121 160972 215197 902439 279855 8348 190190 552893 276087 232001 341013 39301 58118 34402 326779 556594 14954 167516 46966 402568 259619 158 55841 174525 8173 184618 62100 419928 487268 359169 173170 1071383 118173 110276 140677 1105 44695 448220 43706 67870 9996 50386 112608 23496 19239 39936 9122 172185 394915 181175 117369 110066 551301 83700 152033 269181 88786 494248 40003 238216 63520 112560 50923 114579 155700 106346 164069 253727 398808 7532 64111 260239 101224 103076 136297 32567 132166 250777 24930 65643 204446 31839 186781 491411 111748 43429 149354 370708 151938 37763 157860 234527 819742 35850 226255 426129 224600 54898 324800 263067 1351609 173217 256091 172346 1101 17678 152492 24075 14556 55321 99448 238453 147711 36293 39701 46812 528301 82114 188549 114447 333583 26622 2222 118441 311266 212942 349554 96608 567865 413316 43390 31672 388415 541047 162313 20805 156078 2324 758120 7441 37842 55018 546932 378323 282945 130778 69812 8903 197363 58588 107338 306440 144779 276811 177828 140392 40105 58794 6779 74190 31396 64942 162856 168311 453352 47777 247765 154386 207492 425406 100304 3692 264068 123228 89710 50613 260901 181736 80381 90253 74208 375435 200181 240930 482204 111573 84904 523023 51406 259975 43762 91246 151461 134384 119011 137216 149176 754273 56023 85110 117955 209521 132381 32573 534228 144076 17240 154980 22420 120644 202219 8631 136789 160737 153308 99049 10580 411726 164225 406816 449420 167692 152918 48285 316470 242998 47276 270020 103277 346363 132662 95452 515723 73426 544664 93736 77488 245280 162544 32675 56427 58691 9116 273074 235736 111115 32496 38669 67862 99525 9136 48354 2234 151007 191948 183454 8201 56325 17794 454146 387 194484 177469 6331 501131 101213 337019 110314 42335 127439 18756 11800 1051953 45985 188404 166126 194953 592875 204671 189090 37948 95833 47598 591169 69134 83778 33027 520365 268424 101785 15316 498769 148965 201276 223090 137482 102669 68236 1890 130403 6206 781248 577269 45677 283249 106535 14373 221745 94948 180919 343616 269742 107125 84163 31983 58439 2097 226182 17562 16038 47863 435650 358894 19960 9449 27571 234299 428928 503738 271007 123583 205567 158257 255707 42991 84292 359748 438655 62497 4030 20124 75698 242186 47881 152613 56341 72163 49253 173073 41661 102358 63860 172310 105980 110938 1003883 138871 700356 342254 122021 259864 83206 151183 93567 174705 9549 194198 47863 559116 342642 27504 67278 27407 7405 22344 43047 83639 527393 175065 662250 26859 245261 817378 192504 20588 281108 2413 84442 749678 127801 210078 77488 242534 261957 48974 202958 354183 52250 24886 582485 128766 6265 342790 53179 306319 60746 197638 723792 141628 238911 123688 35795 3253 19258 344326 24476 101313 501305 763851 270341 22739 521552 979572 83931 81117 40685 271302 16284 70377 398084 245966 76268 161788 214495 155207 123258 52707 296043 499573 27398 20083 987196601 830362742 739026623 392083710 293099141 908381716 79631349 142746035 877271365 389954644 677816194 615570994 189951089 837285605 612775639 263247084 301277175 480909620 292913138 136653962 310168334 910204876 813326729 450294917 190693326 894276219 976055746 460398044 98228396 964638553 757897623 373850078 450514281 279901881 980024876 287737557 47661051 879622995 723273174 504541896 609236481 423454471 439852836 26222279 592897595 990334022 996118879 524566097 210282159 198175573 778323592 650270303 222699929 711825327 673897092 993081841 159564174 754152064 137437760 134091124 830908479 102211933 104838124 136459031 322529698 885037818 255483998 773096996 400882501 192030 361107236 280853469 868548069 547854232 824222842 190553837 979163374 333399239 222327347 444257605 361983846 454485982 700335880 280569693 438479773 211662501 496090797 596434470 961595519 461484381 351821716 627968124 909921494 14953229 955086422 892467591 449625797 127458095 268043721 385682781 905419620 393763401 647908779 891011379 58437141 60665055 947148880 751704585 61477388 441171257 15960481 390281108 992748767 135101268 250212999 6246594 760904342 923024706 458072109 875153437 443582916 363336452 34074329 241777131 511199610 483505273 806625134 741967795 908196190 859643276 905470077 728919511 931885931 64220950 54818556 372139015 457518617 646186461 255703143 65290761 79946431 12397232 127459622 536174268 630704074 191914423 189578327 8152262 615877515 731514531 989358918 210187014 572067854 467066161 907694542 84942707 22358288 796076162 868066466 474379666 159451563 515691639 601967662 461067231 981316813 146363168 692930628 509663998 143213034 524587918 17994338 781302321 82007570 173157255 348997499 174259233 482584509 165401950 575782666 310688450 216272254 890031539 878627157 504767275 520604671 780487148 536078623 929436242 868200090 158132884 773975422 481895 144179995 6228206 925057956 249630000 745515006 995646504 78296402 358371542 834274725 37204892 194722257 483264355 31700011 130723520 195565764 995727878 64135682 831012427 933994048 215866442 818935465 918473243 57199750 71214738 583166293 537616787 406875599 363734326 873229350 410556049 935182903 906668730 253569511 238433111 146689130 430766095 311346341 711930580 346020173 974122472 251762363 347628383 446110647 987750309 399087896 654715873 446323169 338507088 669985315 863350567 680097876 979701826 814954730 912828909 700019155 536498544 441301032 38646689 79467992 215016431 378620671 4889378 733145218 605808422 329044820 774286246 719595726 299109900 147422534 397800384 427330901 439853208 714517168 622217621 809551311 408863054 836175107 17228018 261564338 288588571 663602682 145387808 714418239 940812261 935154263 819886858 576895382 902555315 300281035 512602448 456433947 976543824 104427593 693768432 224461604 348608489 210063931 724779398 689900367 362337863 582502970 178787996 115722364 187373832 890658081 173680789 53378087 157102988 702959441 259260782 899538275 904832158 428374748 699943868 185660311 2552450 320261394 562439984 99230925 519189818 291788229 8277615 676861921 122310287 955389554 490823620 420162153 579719218 62566794 649948816 381900715 668950076 51853216 720131891 994099189 505727617 192838902 246142447 129911994 733732200 326747734 896122026 969733807 102575331 67127788 446082412 839168094 902537137 108227841 939048745 721113583 679911315 496849768 329294516 194842394 294209657 33468207 815141001 97724104 182211497 53637053 779678804 935306097 166419471 10979574 487091094 478653937 595391982 255129984 577718289 396547874 552942152 288922093 359430008 236991783 222936133 883805996 230881226 577934103 129291624 439968781 645888691 464006797 65774637 851459633 108713611 367619674 318509190 595578305 208049581 447732055 604289923 780223962 101000017 933610887 648817192 400843231 111069421 655351501 725548470 405329137 168994052 49160344 321035 627489705 221933668 827917349 508456271 159616522 115596863 613031476 276889317 123038795 127304861 854574383 452398421 90505310 754430243 309970041 722334453 261372433 190449244 313533789 290230619 885333433 581508709 731560628 483935475 384543801 637996934 535049766 684283669 186319901 981883489 307878254 339713509 714610993 270623605 926735309 514416379 725655517 450417865 720540188 15996321 873357910 661641404 22628365 724189881 78980945 681583061 924581490 329878417 832529701 523765849 828734067 288476211 398127626 450991885 21715450 683302603 78173148 750708778 461381625 313859782 216574093 494233596 414203729 197590813 610983845 940829477 67574291 697296049 5296062 958847445 400685920 848801089 696657491 64051746 730636294 709283412 412788715 782124872 896687350 543033554 457671485 702891283 282376808 198130822 22617386 507846567 320491925 287731006 459295920 427486062 262390468 868119141 772355817 508166207 415927034 709878102 454459975 340040924 254897449 894645760 539743442 373821108 364850045 720586547 581637792 938213536 699989193 429522858 745718307 726285767 721865764 65949079 972519669 924560465 473113823 812562240 113896825 508570783 907097323 636857611 291848948 500136967 882220153 692926958 964462122 9626392 814724308 573758965 275431670 584998069 835113064 969633480 142933600 906822556 355901208 19096492 902259736 575284521 661120532 385574016 306486089 236460059 57095855 698599651 851118882 905083279 312271714 727346117 565971580 873781732 629873914 443124636 950719695 463129861 717312199 892645153 517372169 579461677 494915175 744589284 324179196 998215551 448453616 218040201 608689572 17608917 314769789 50699176 591444807 988046364 763262627 760557962 789287965 909005513 712274065 895291744 914596168 892677869 151121207 451874938 720839713 332200499 207835023 755271359 311713569 685475928 486001861 477096609 381352423 672933313 198108307 457139705 128953842 814146145 270379791 670254293 254827614 69852664 705449007 613417874 281849293 932012028 387449508 807594772 982589228 280257332 26712828 571498300 570900281 320978410 327335818 890391564 436148147 533963262 782897041 941218557 758178955 919914678 277822192 931435289 277218430 667859413 169695507 939620224 771601812 648132408 543272195 31507304 710116347 671365526 367823131 733316506 366342925 63468447 643055130 312160603 144547962 241559909 545967935 756676293 38500877 263787582 736448730 67880941 471754411 899092365 334647798 690512246 77166064 301440018 530833299 997475967 219645694 398888989 719505605 774015096 755734858 653535084 219403256 951681131 284163957 364346687 585350117 250473614 283850052 320604385 539083096 867443768 310319007 64876170 331986272 744268719 723641506 95936993 15413114 633139531 483373620 273064596 848235443 176426102 167368838 313752564 284964834 676918366 412507807 499267996 948414155 795471210 98784897 532288068 949802487 327095552 46145747 962554832 565954142 315567500 15011492 7128947 515111604 249650527 25561605 944102874 676602702 358799120 259506232 807159637 467334561 398965114 482875918 272138557 726773808 197678140 787243324 228709676 413643495 907541093 89391242 987779578 466565416 623412051 635559799 321751604 2583817 848914425 660176870 659164320 840267925 210009616 904178466 848039788 342207310 174647202 774656461 740081773 999307911 338201652 390755037 980011344 111454591 81537069 875092758 873857537 612199042 52859758 198773521 106197130 619325182 923897725 548695986 558116729 862852225 331142160 696832590 270863226 855119924 108631711 450774258 301478061 676882123 662924026 20794048 109698965 895054932 313506273 233089238 191126690 180332466 112621784 147373080 319774826 330526831 459479650 50738657 372609806 931985100 34601851 289629685 52580476 592981210 414023415 408773350 866404477 179087666 874740986 493261225 181632968 892980509 735774063 314818643 371435249 689127524 127754649 199521083 910492336 886817651 336673354 272582811 284521092 174507218 697258640 171111205 270978491 253115992 957691787 135044383 384864716 351521490 907609287 566717325 241174027 628344723 27667701 834211195 311192606 42383630 764223542 203655220 924810203 81713778 723717128 102365126 709633974 330446112 300105341 751863412 489974173 99796680 320264447 690540871 732086710 333961332 345360651 592491892 131955192 439733238 251505967 201269795 669656892 10418959 689356064 610890202 479224663 308640384 304289061 539906610 941483972 830207551 780560805 460262207 137477454 762453312 889221774 661807293 963706837 418192402 642271946 226137264 368255949 387646768 18878796 361972015 141664637 272179486 213224974 387143869 215059933 668998748 145907862 633431879 333529412 120694991 585291270 419950105 243334616 957203748 474157601 996764160 626001384 269496454 457514736 61612388 698105688 223925719 401838867 391831456 400081954 303614073 855626626 257886723 683867071 59407309 133977766 874720932 637080094 575509963 51256607 212213799 967187571 675987459 10850434 921302578 983287202 908034230 7741786 752947301 979243767 49677515 69090205 571694698 96765456 207130690 757011836 241221836 729203779 398753430 166280469 981369160 487958940 605035807 77699098 741381423 543940692 401361898 23595241 940137594 991818195 207125906 240854390 89189784 885071596 971712916 564927419 329663939 353164369 867610319 288858516 664485714 489973534 925451239 164094695 603249859 400405394 78689709 266998474 808241925 171839192 953818730 296016010 910936537 786211842 444672253 229510620 725308895 173247937 541458257 450354471 276135650 245923763 112394133 168440414 820302988 83428815 296435495 330703867 255114254 146445321 131914963 295883452 800508664 710306764 888705646 881760541 338707119 138820295 557339803 677495236 652343686 996119328 694211410 715462484 655168783 49110503 395084676 245994802 835160347 436814700 432441656 963282912 4007368 324111735 893196015 9595832 832061481 608694125 950575169 488561803 955744300 674923710 829475508 997145356 279540873 465147152 966940925 761170156 546675946 73455163 90882057 217756429 415491227 584925744 747230079 217737450 888676084 699350108 521257023 514403604 885278243 727732208 609649672 382392731 623101588 443523004 809273896 988033869 595729893 707866467 202449167 11780374 546960557 943381074 112291572 798472354 951657592 315144915 404108661 849214814 525999796 105167544 814173049 407703311 642711042 94190256 383436639 431240078 488030327 360445018 682896819 978720557 420624152 404099438 37817876 996550373 875666456 934291264 683302293 650382273 955550570 34997804 127292567 732557448 59256381 437440222 67056948 693940254 603332402 422647693 742013733 165653106 150549404 98897261 109979475 825258283 74451757 355956683 723258958 977405254 114021087 312047200 910879168 5284512 199544870 13843305 289922174 777939247 313585216 141126018 308004809 246314608 783849137 724991487 532188405 112893824 402807620 844090743 930889789 885243498 812530106 253517058 629891485 353275096 592720276 219371415 601197645 159476579 491267690 758563271 670302859 933184011 274298664 43798353 126770729 838763911 843594379 661508233 947541992 318852643 254131879 805285541 529160907 672777779 126407409 648726525 130330671 961787746 289246009 536749674 23750575 415019991 387511537 909342665 842913391 231980494 535482118 10097027 829117637 730263422 606839633 806835933 690094504 701637466 737531923 451349105 826132936 808528385 960871664 762832474 297964964 748860100 277022327 71263003 366690179 183404203 778680738 988227140 292930991 18653057 417390166 706892916 680758333 665618330 515535854 46609695 839823019 67019748 663943700 976793349 126690852 437172521 153749464 969992012 696314754 341673137 993958810 462652153 558375597 800791947 935792804 388712144 167777870 976756006 353329336 515532480 526315253 520906884 692812602 694360542 274799020 870245071 761142186 813472474 225013641 183506880 557993310 38028261 479456975 65284582 192594656 920555905 592329707 981926890 106950476 709971082 263018074 931142284 237793460 818953545 2066848 38742829 826471711 550915287 855635372 107446885 878668393 373056968 900912464 947747685 489915211 174720367 326323627 232898957 528031393 901061401 873468654 722953419 75324389 84694657 561580773 452988531 131287830 911102608 92232177 261954196 628089488 921228422 292728924 506340491 759682637 652249931 313984207 735696699 804739525 473215285 308172830 183976211 684888003 937954652 822558270 396919498 351622896 732054183 393932451 950775984 720470949 88280114 718185846 474167337 692984369 268001156 340633172 60408912 428839963 850157628 325480023 29468690 72698645 482424084 483288128 670960124 106189437 576206314 796169574 585817716 479187217 788068913 983845111 722611553 524108971 885885750 720589369 222464461 153424271 217330917 752039369 119148010 887413898 305867163 168537876 710916483 603499615 148665253 986791918 195473562 673766218 588440918 470008424 31259266 673231316 266416157 612932207 955969039 794307450 684693527 951033034 519419755 610492579 177334321 518109625 90478419 667977092 783229606 570423619 788067486 91450443 560177460 538118964 406260155 268841056 133495707 671587024 194646404 234331348 688893965 119509052 932543617 600292159 416737165 17230196 781006635 392481570 127554442 748220874 709181132 426428213 836843187 953764089 894849875 415763797 288825703 748353206 424041276 926872354 608836659 999475305 712194886 280548914 888473711 612075302 534593570 293727718 880237637 248310359 313583519 709459670 433771986 953996199 750938282 307512621 696759442 503238215 531287924 334502591 704205131 919790987 275763087 247802083 948365843 967053461 60832121 297354219 884596131 224798654 112988582 990621049 639052920 314965230 824682518 331833762 402583736 771712893 646006685 511272895 976614436 252264554 505582805 294511043 645681455 862305116 875988479 198846882 341022725 293908949 997126427 812814688 824893338 884462854 999239413 438707048 633728155 660381086 277576154 362540747 971528481 48135502 35677814 988107819 355641842 297028857 809775050 777437320 419703441 1697070 30069818 463489296 476056729 874432831 208185660 980921807 346324325 974539774 79798514 385837456 460835073 153862123 975330026 886527112 28992127 311739290 619483903 414211981 76971319 59667990 965212912 870671762 902791388 881819691 237417819 832974971 666027409 736569927 309531884 353945119 840563932 961070075 265563044 545001208 277849295 571789177 168346267 883126790 412011683 380583852 968602466 76616074 193118013 863008047 860566647 622726138 496541597 462987056 99824196 291601478 409511101 914485806 959384938 778069362 734141907 151367661 379238637 364172037 170042084 114054085 948112200 289921300 435761025 615141840 878059713 435803265 278892427 235482707 199630408 409805741 35138710 439728155 84110410 933560331 697112753 342766531 417325895 392807586 216473486 412270817 824362070 607658869 942994323 707827491 791831028 865922564 389033327 148533756 433498198 389452418 308007209 753180913 434360640 35259362 898914795 616847494 318149588 892420876 283983926 913727242 121930725 576188163 513659004 126990099 901605278 304700495 529992083 157220363 710240422 137548050 915755535 388638087 117238197 197825579 507924916 300534718 701236293 365205227 29742414 679906298 2889802 835206777 197251581 750119778 932958699 167896753 397793234 174346786 513640955 5909719 934307803 309637650 114033202 132498573 100082010 713706590 711879379 414017025 901254138 792988010 882186772 237789720 657803124 646787176 823676868 944445233 125269756 692501656 26891158 346630356 592233828 24952302 547995297 936752218 566510099 450503968 377405165 101103228 605534897 718525002 56556909 141559081 877349464 975114466 361913447 858192245 94643295 549521457 67736640 283630790 740370376 273105612 492545141 78056941 360413754 485547976 120414507 957886345 973666531 780518414 673348768 360081856 246390856 570203532 224598537 261446056 634704423 419903247 704566798 622894599 31783246 392580782 35622534 670695006 242824864 102545853 612606462 941050589 852952532 411301214 266097496 648140863 628419051 11857165 425179687 546809954 592114526 367470002 957258843 31847198 995011633 306078580 743500061 669234460 693473013 479277441 973815888 339386719 728945008 302147510 332923766 205412390 288861608 490561960 557818877 860849489 903912905 328396421 221710865 406233098 584546654 373129920 721669474 419723929 332763528 830470085 294395654 466456870 344481068 537822500 458346966 191754530 86679629 667377679 828157390 466746141 685446553 797027223 402269337 648709889 597882148 501545735 796294142 229676640 327389864 713149564 844890336 522070352 940234769 123865538 677992137 918609713 551708326 946605577 855876085 874711284 247200932 558930050 523542325 126897266 955800205 822440258 687040501 304409083 578141465 991674568 504298589 827067693 282904990 152957501 357554625 729956611 314680519 418027550 380037748 613368736 793629156 446331236 107677685 912290791 835430047 892235155 529105121 107294522 201425345 658256835 97274789 760186406 296464519 297470385 48228258 719165636 564810104 416472328 365453036 792277537 28952174 770454076 835703223 722093199 443434767 53184862 613409882 381035132 921808659 562862978 142303916 423673556 472983228 340600761 868292482 186122490 360283476 395793940 199472596 311699502 486747582 600847656 511312570 638640292 22506573 356142855 787913085 295579777 283719000 437550814 39711076 554770168 646293831 126167234 110496700 945173554 360387309 830946294 802531039 332855915 117877411 470486972 637557076 668645422 707787504 384584711 99669443 606835687 926880487 408873960 74477170 979025259 324188060 857085733 556101628 982815940 805246510 51166432 179049573 962056844 852286851 673876861 10678303 688120851 263883771 156504441 648933188 791216448 789035559 669764682 226696891 574225059 815911723 232340040 658457468 918537828 3003124 797405670 284095373 393752732 103616151 337473109 194509670 174705285 723404766 874492771 948835088 861084263 766381869 142386514 530272405 168391549 564488223 46317429 888986756 543683919 376529954 629780723 504202648 328113848 973089685 488291746 87912526 234417871 348381138 425829623 811501723 427516660 695441386 176084089 95434489 63249388 575409127 897524060 419710757 458353822 493836096 916880799 26836444 994070604 810885684 188191748 798843610 635163810 971546399 900309500 392316779 920755842 93459436 369870897 692628051 149629327 356214230 204355374 193688055 724699417 295251171 856581022 71732629 11217731 282182625 562792971 828559068 703382212 788010529 959569048 632648235 988962546 149178607 873334969 461945018 509193157 321237687 197209505 292963147 358975196 332049673 923399484 935118202 568804721 324905517 872342515 185410546 267986690 931910472 880068695 552987308 600392717 611428651 116700954 314829143 165969199 727744692 219281676 751781382 408997266 939846111 828054511 788166043 883652 828576846 781081947 222758505 657735813 911930547 939902570 963534410 38858896 283459251 557026635 586560866 263270460 565302958 85986459 537706158 480195587 318319136 82655612 509373634 983548773 628376950 775339453 186094354 447874049 358621192 207419056 230539637 477037970 792611519 584997159 166608209 552686099 502046751 549978063 565909380 897397247 102194242 427444080 934582873 926468411 910646452 154560693 964864464 382002471 261694561 258912835 683635392 446746730 775709527 490154789 318478817 151164227 637362256 975329875 173472772 586752092 742162526 74538005 234592675 982819830 934846799 113219669 101839224 227426422 43777680 726478319 142633697 984735682 890992239 299400538 838323602 939235778 89138740 548586424 717095493 47284401 474805701 697135161 397648467 299579642 68309218 409702313 317138879 746395734 314354829 937327537 420092327 866503925 993312179 831381477 44400775 812432608 463918037 30735628 485178351 650889640 66447984 432629216 159120491 861197680 285655475 721674766 340075504 520996927 206699551 438268238 65141125 508055955 725250039 593788496 947801644 263671052 98578989 751882052 820363851 187516676 770238853 313597339 177134836 415598727 611385423 610965153 963490935 773871125 89924791 669838351 748998140 98007878 723990646 410460168 328053508 983846141 285941899 234785383 699231618 347653415 797962508 645005079 729074083 284836525 442888060 896538156 855269136 186788899 792355605 245794626 5536342 287709254 808463317 811653995 243049921 845335093 166117552 783494062 824653165 547739315 534639674 969189687 773714552 578568938 186735412 700154001 179288347 233237627 720340762 629367745 456062962 310861026 870122615 73190019 833362795 47815868 881633871 281889037 232516719 252690302 690148260 26468623 721168165 585296202 307268955 576990785 587808257 536227823 672695127 522357206 745785568 275752625 675777681 167728926 308259759 935267852 376464358 509769605 833323717 38892925 377150262 231053508 623744106 32111365 364951504 707819349 475042711 940597994 691643623 221677930 775606573 985615764 204539388 508352897 14812424 857926931 317950471 238308810 8752936 454174491 914952850 605149704 251667334 480312528 435917627 965224110 360337896 27573880 561819359 840936551 428603304 373570730 754324769 886728167 490842162 586300299 590099852 50664622 762594368 959623947 613491328 229744204 793287222 798571198 62235422 522021139 396834238 168559943 305886576 288097028 88430552 306596648 885827403 154142385 47594205 200508442 511687181 736302783 619897090 822232474 809758050 667139106 891686176 709777764 456832972 443524952 649656099 588568045 83588392 75150931 940214155 780995701 721743725 867977251 376940961 588229718 523871413 321852483 850072733 685945221 202793551 654264391 639188897 995759308 361185925 154547023 918775767 756109645 875152580 569743960 585193046 486248224 450796638 934411625 934728057 3615177 886671529 237035263 868588658 337314230 326738278 990959543 743091967 862110683 234933474 871281530 53121420 992313877 419941239 309513847 611140262 549643282 216068809 561320871 848528423 318813509 782753604 681718645 158413802 818571511 278698072 62152467 594074812 834940704 458811875 597828837 294418413 854652033 593464125 61237523 366155365 644316178 299942427 46724140 36156650 29704835 186161592 391150067 870620806 146271346 754556233 62705703 889792481 299879080 910858371 281213522 150549034 944078458 191098013 830335976 15509182 239238401 404248453 755143964 437396358 366798768 195221980 75952148 698855072 64904715 919349338 839664439 978057585 33611757 971764390 801709629 626037919 569579134 294563484 985707361 94539099 195017424 916463680 81421593 528229776 401962408 352055388 435961136 162561527 734779849 198001908 137140272 658939732 54245895 481447710 366428735 523422675 14581380 176742739 500566651 794871497 141029746 791173282 432861213 928749357 783316903 949726439 524544594 355775411 786514603 260073419 257561660 280742120 777120886 96131820 457886762 413095009 955397712 22577519 349901526 606204280 658502204 613455634 478866890 809099048 348599339 685991406 822649439 573007615 158129293 460252714 147944797 314073457 855093548 20455435 807967442 215359727 152930978 932915820 169672844 916639648 90135435 974092011 277556918 557460595 129284084 95394918 474934253 756984275 969319697 288999343 199224181 845002399 302199408 572938386 531055750 920758222 176668606 775688468 371389792 824096511 520284232 874704133 819457944 177256874 516400266 971560742 631786386 490533990 993044921 941930880 74085275 689143745 726745460 355962763 527050910 182609290 306516963 805926803 171836333 199943415 330982999 776014901 691234427 276843089 833856528 738526215 389294710 780849129 956008473 560959777 790675211 910900473 67235684 180122631 545203319 74484449 23836549 336444250 4795699 131882418 725488135 514613313 975463045 161108996 199986596 501168451 50340091 648393285 368720158 399071741 294472695 428195131 835293213 100378302 466185953 337320638 523031344 539441978 677021758 653963487 789951060 797694756 898357034 608488942 195549326 984341902 817159335 537055470 600366714 362828352 676516286 920117424 421080809 122249305 541337809 367454605 62486720 400837048 403303724 59309753 204297283 771342938 119841468 353255255 400645802 663649668 684518324 804337541 170575441 318994499 988499777 491369391 863556135 835069293 612013159 730464172 15335554 569868979 229445749 65439244 958491900 664818726 125605036 876027207 339164674 45191598 347519727 442166950 598239451 915649106 169385798 496894892 909435071 477691670 879286235 97595864 598606839 872761797 178219627 125650609 866696406 557567649 473248214 279573817 66512643 849685857 606305366 487967409 872193336 225515352 626920955 20099130 382734647 277251129 588911689 883086106 50072560 230607008 758558935 174936622 704579357 895790377 553838515 540650465 585625689 522117300 143352358 956182107 646715186 517599904 915542393 815125955 808729173 543531739 803806030 923310479 915122240 768997799 846342087 759221193 687471616 892718313 983909325 213334110 37024499 878077224 62628392 533547143 637418095 434334125 914080020 333062466 26146478 83671528 217831381 46345635 470738234 315161575 500056471 508304475 310766060 755949176 956705383 116789049 104348976 816129554 797280033 851405582 488840382 326268890 865792720 12662418 609846466 596344109 968940118 282257372 4593770 224632306 718242927 71322194 474622748 181359959 164072649 364446864 693515184 142562697 291888235 493261532 602372532 517697315 408055270 749828651 619345940 343234760 836830560 497530058 34890939 318615479 495639190 748767672 691125504 749592371 732660801 23805030 950938333 650198786 257673723 484352806 765813131 12463163 546336247 927937086 162651381 856111778 742837533 75531243 317376763 260741416 544257175 56975648 956010692 67343309 840655724 850772070 60097693 640364114 468359941 328365247 157645848 894312939 658556457 473283417 379323862 261560063 577071757 516894541 921244542 717825797 935005288 931450390 788915169 44104680 695312693 515091404 493245334 423340528 732891963 195366973 703126954 891204110 160160367 866204791 828700169 628927055 290827410 988424069 239680128 663976379 121878169 293079216 534234266 747972070 182842171 365534058 967708343 970545265 460259954 77758480 131843993 763026388 478623352 346360538 762822863 406070952 26198309 938390380 123056474 286377007 224100620 710213752 122103846 271809748 845881542 855374642 913355079 721007647 499514930 428894303 258073282 899619130 429131208 602755945 965578140 281970909 877462476 649763549 592676384 830672674 359586678 342150492 790904087 669802324 615064185 396699379 264264888 26916739 745642182 955864111 717749518 555161582 496435544 393884429 273616591 890557214 752416857 310685663 39400954 122663484 489974348 138437260 919829376 514349157 66680297 599032862 258201130 943005220 283945709 948447951 590617154 313944960 231729708 294425580 557597273 217404236 249887757 700995796 352482352 870655168 274624432 42640395 621421605 949358117 750223005 322756369 943917377 983321072 76605344 401971592 766124289 258155377 51442254 182900430 427740439 565541018 787485489 810816470 687384014 3997659 525323822 946338317 925599728 15807227 740719019 513758883 198810782 563726393 803252356 793302856 772956226 686940288 934093587 108048760 337849263 534066446 395122493 544073660 227685763 326712731 638713682 463643273 845994822 973466569 774712007 441868538 479906673 653749313 853162204 587204439 135362636 717467280 720391362 322111158 2969659 997756145 729249625 490283328 560898347 802407467 440486491 651323301 393536093 234885865 478142197 2030627 236613297 884413125 752991929 577325844 296938475 593339588 557349663 817550872 395498737 202926904 409618667 827555056 886140061 700025477 623175294 764952366 63890730 838253882 845911667 254330535 775923279 250916005 957739206 440616232 530679360 451038205 641951568 512386025 668876648 390229337 647283303 802879850 120715669 132084117 515177747 972792729 441939068 505335563 7141898 305576262 48128712 115778644 285743601 308155405 716044410 983198479 187192985 931849544 348450623 616926240 624153284 968316952 336475101 261743230 404967 152833046 324895636 449982497 422934454 817953391 862033687 900995578 804162044 419380445 232452797 758157518 234235119 15944739 778123171 797197208 219650569 228458343 835693473 927274940 138370026 582632387 399591455 189135063 796609269 677401859 128428557 887700187 323693227 549491127 573537308 411037444 107738312 722071756 64539868 497742263 911781440 193873428 772170804 856503601 353393587 666673452 796356618 496693686 69605718 327695683 561036590 202643973 112586102 942866295 132962193 908322295 348266350 46294973 993246130 164100075 534134088 602593446 246095976 609325527 813638863 753796489 627859895 916167154 859006347 485346284 107171265 169160413 280184402 324043964 751651570 463674585 43475345 542023096 523882192 207552127 702249412 172852729 541642241 252994348 495701363 397473395 331111259 468124803 760221005 176904543 981108325 571021022 451235455 127152064 937227642 462822674 663831827 45965475 224508524 965026201 492538048 783217256 730149874 368281213 134629556 490306742 288065711 313224637 898287810 691814947 555229769 449150244 188960794 766778176 664290894 867580828 934366742 229160180 25647903 273942861 731421656 281510902 292492875 86726409 859604690 735707603 363384913 566167299 51913041 336667286 458479478 766481556 98391665 772425899 565081257 349829611 907158235 416524639 788283918 861761143 942069469 59336741 13823942 775827353 907544812 391636029 914870868 3551143 591789803 370266745 436401398 574386768 528531413 414003265 682729420 852347362 562386299 705464277 865552435 742901557 577364011 928787108 587576638 253411255 226535010 766343125 727611128 947052884 269187785 199308806 94857283 514902253 170527939 931180654 512314438 118006502 522046497 859087064 257565591 290925396 238425764 702114343 300954430 330829665 241194621 928945190 887172363 793741484 731832978 995542739 295529388 886803125 294743500 573437902 108952748 993810958 257970555 889876606 609802703 333206152 446768056 128743119 399748008 272684513 380587383 503107650 211455913 190985167 110114994 378413228 228114296 108007488 644828913 193794289 585678910 603659366 891751605 409630834 382658626 587533804 563534308 210222992 688005004 861074309 366408637 465862446 413559283 308946375 920718004 46456967 212149693 376861517 648553393 243700261 299586758 334984778 849051959 943425146 39481982 471827265 388916878 236908410 633061260 102519562 263211579 791603915 342424306 294649720 304136123 979270149 788963532 175011211 613033198 274950364 910480110 645469919 761284232 763776127 498215395 416407888 56978433 84549036 413314214 273343838 679530477 67607317 548350622 752084798 401681495 631891171 169030557 751919426 921089973 907043440 799914593 212319202 413266048 194289836 46992617 417543404 930304615 836312857 206322256 127388939 910391339 863004469 204180757 411534917 155446535 196322264 980596650 855291681 107130961 918580894 848868888 791437753 562054525 593325192 981107962 452256800 535766173 981340312 636713561 121175915 992547196 842887211 430639452 115498911 726226380 630059034 251269966
