1000 451072345 211732721 420423194 428659228 489436948 106059583 179971346 412440123 149129162 297410355 256300590 337622506 195842172 275630014 511224440 491878481 341295135 385095856 76022293 325863934 8751302 130398842 73675641 431739107 84116445 215255382 69680715 58416280 536293516 117175783 275378482 450494950 328908505 158930764 342283267 281474541 264990348 522254614 157043752 414119510 282794057 413344343 214871105 478636229 152103446 189224634 433643799 493398581 37449578 509666092 282391603 46200881 103194022 356067245 477939989 187310468 34451715 10749792 245726749 33874320 127925576 521105231 484369271 456834081 143165084 289781626 201437711 408155432 275165328 358481464 285404031 21088473 234954895 500275136 499724703 387058341 152628858 396497591 343586010 190078437 369292771 89106702 236279319 472486794 445173947 177348396 122926350 479625662 188098188 368653099 513499983 316023765 352887419 460998342 235986934 496052503 213909056 437424646 367337023 489074384 259035198 115870142 510162858 493990094 79274366 473016650 344177524 231903225 332643329 150892623 421981663 165065189 239999325 121390070 100681071 148302360 298738466 223607422 91057111 486836654 55389610 67686182 265989507 408277029 528684524 501976442 367458620 205722668 402530177 197924731 157926141 124694464 313794874 131218088 81813646 393069241 67363826 425991170 88101554 400007156 40012882 510083217 28201433 280012207 94602375 128882504 428314567 393340842 352489927 519371678 343306585 407879537 50186949 72425180 279285654 42000561 37530711 109873362 247723230 440060888 307798094 405649372 27884441 84722057 536867460 109698087 477791298 67360375 535689258 29021941 467367531 38831228 2234246 495568964 318843435 96836622 87580556 210287091 490177464 440070484 192787858 296613137 311079109 242974807 369038318 53493851 284975368 406569030 163367214 532698598 309759007 471165309 401477058 337643448 19016454 401473607 447341535 496807752 468833982 446159882 525829694 399330601 484991110 528063940 358028653 266963634 88029651 445609210 477250726 41336204 348808782 133167672 337949342 123016979 376142479 170116749 176510831 124246935 39814867 339878045 120074622 349573874 274172443 521551681 150346411 293188897 386154376 60817034 253125738 318117446 506976917 242084520 180577135 455097116 233277549 1734876 185189838 321307201 447344087 125569652 362643405 259281957 258737324 163721835 382298936 98008892 333838585 21938855 222255827 373653452 361816901 342330450 186356415 99118432 327011219 336702826 392307330 176294684 397519861 108562156 494412130 367625866 350646677 138118354 285852070 47053314 139853231 471041909 368360515 50326406 59740650 194133009 309608363 318477974 357854844 155036387 416486867 154822517 176975243 101871782 528475970 1921232 444202233 177961473 101039665 234342540 514664299 493346995 410637224 375313249 65038239 368178443 206068203 415684917 506296797 491920273 462738231 109279116 426091271 294227835 159605522 485831921 488360844 469213885 267438984 309344776 87379361 147054939 464167294 264354604 248926721 455772353 266275837 156258043 96862914 367315502 390600584 74656302 323791585 264366896 449969551 388829825 95674428 119166843 267643830 65100313 74216204 193511149 174379430 500307476 487738984 333984952 449268485 439228916 266327926 179836557 211702781 353707287 326891496 138999164 81190980 38947306 57900605 347466817 195205349 154763520 177911407 48935021 229419823 501702993 313301918 142518462 353661906 408976346 261685305 84434824 474076660 335901510 277945974 111585178 299338074 228814047 445570131 211735647 131172052 175027145 391572204 342874834 528734433 181592788 481873998 73054501 220540094 2903692 420521318 415745444 157667212 61561813 464680465 387087035 26393894 241111471 529605498 380055801 113216905 254419891 464490626 50422653 53450490 205565688 162007831 352788564 434379736 70707050 27653300 28680876 245734196 419225505 371555710 237597717 63947382 316558797 310652218 284487477 319462489 194302624 163362009 477129702 255864438 91171562 327345825 282258333 332283033 320080412 125443222 445499938 37629391 53062936 495922592 91079882 258628625 121059511 443868447 156137449 191766562 471521747 184818325 437500758 353876340 19503124 138227563 417823723 336061921 448879781 165440288 118653499 106311493 328802297 58912289 362175932 419973859 386258115 107563353 215385980 169467615 233006576 124015007 207097006 286069512 83066687 298176889 7827225 204126198 205174424 163964674 395892760 139825259 348783000 296522607 493701600 368286125 434750170 374654411 167477134 346759039 3223787 286130633 453070533 332026084 345042923 278375553 215129031 194430126 385938907 430515012 363897741 82074571 17659107 34123835 368144083 100725794 332300725 375971309 304851992 604237 3065072 163873841 140429497 351848073 460396448 97260185 183263286 358275707 471914597 350740420 168163835 475138385 100000142 84363456 270293558 445043065 362739010 485422590 102602279 211807005 379066690 466500020 293881577 396725797 500623856 125154749 497451591 296053669 501126058 265432672 296657906 504191131 429306514 437087403 319168292 352832051 534347589 502431578 174236846 469391275 316301086 342400681 407658748 416301229 426764138 141081394 324473382 252632236 89633072 427075661 464439242 468699762 356704770 221449907 328554648 320457714 346604656 289135328 79640471 310859803 17697088 376298378 278180022 447003603 276514869 60477402 262964742 273991547 26038068 437201588 206511910 342339155 242731358 77299746 221769472 132624584 218381141 9371942 385256821 308014214 436447604 312825151 239843065 256281462 534275059 31526801 39868264 344008804 320662129 119508736 117997695 338359218 495807114 396177718 248491909 235451072 456655120 511456651 509442619 482693189 411787328 179083617 288161432 117647775 256383364 509930904 250272359 474764506 519302847 98658268 245907808 418879539 411483420 485750873 138290089 408887567 517277674 178158354 216025459 301068892 297667090 334023155 102557198 256603293 193329961 351049107 492054365 113114170 325634847 464626073 58936447 200551264 106838778 347097880 318199039 363222143 320157872 31600486 301115737 302589807 130258755 10152634 184598435 4871263 495903507 322888524 413758831 476310270 501046879 92913379 240508250 261843057 426936534 343065449 518446351 83395584 157243645 473629804 196509755 482878492 401384965 255446203 146558844 508223744 65673171 464757884 334574976 385831044 496358370 98819801 151549939 89746214 108972436 336148374 94617477 68005031 122165987 508376309 7444390 86341954 64418776 247952640 348185012 491355311 54147177 329760451 37879983 211390822 266519343 234389738 157398403 131033397 489835942 303957248 102386229 18638201 231844220 436961205 404469245 191331679 535781007 19148273 281077893 107882531 355296648 375695371 175887563 477462635 347200768 183331953 26933678 411619544 431284594 375118690 366103943 485431772 168008229 403983927 159951683 434527573 101502754 317350086 28690058 54467784 84436422 131076288 73105985 316280643 31166582 477575231 507612322 30076677 496723504 251819304 137959209 315149240 90643763 313846772 255740964 437844532 497178726 282674642 312593165 391592408 120922421 141826197 340153268 288930651 8939212 500104951 186587312 110441967 280584125 215277371 164909751 365020548 346353659 238015737 144430280 377520241 178720056 115171690 407596919 138572649 366990995 8685216 453721890 457634759 322531988 172591942 358608379 282839802 455266585 134330633 137561299 39318094 276156830 477714567 328248746 285096043 440948606 514836058 395538010 184661820 193242518 23576849 12811457 2725265 261592586 157241737 380245507 440312643 272413428 250971514 42014380 102533511 259656731 495736270 23297358 45317808 131457301 381905738 328157610 49852974 516236371 465718910 89171069 255522289 406562565 417419815 3747420 310640260 395384962 399285430 495302081 51756568 422862280 508113538 54481833 147583955 128484364 434727341 51025686 400897792 148827944 93040067 503431304 408484675 51905425 526728663 453802483 183362726 371763489 245089182 233215701 351128949 173937180 322386771 69780327 43628833 202935674 73527747 354269094 61449724 472813178 312700263 113206292 358804547 283942889 167688126 506388502 412427254 65544556 20543277 276454134 214372500 113583344 243014527 85986263 165488770 232872278 2917834 348851497 67764856 248007016 45196286 418893805 421944196 367583057 488674133 465573030 33647820 25330968 282971212 95097544 498144147 58800563 208303837 320077782 342743453 375991964 289595373 218299795 441536520 310138650 494753930 119038108 423721995 200897545 205024371 52339853 433769824 207942206 401191351 501534680 455949223 446387637 383557574 341022508 277099783 335360795 269724626 310747603 360691764 15824927 405845148 321964999 74625490 77278074 105171870 417368944 453270038 394767244 98797827 357935646 168034983 56680845 476973755 54886066 257578390 145127215 107225920 154477302 353069421 508417271 119141071 272147732 417933997 502698645 76299328 158162869 301188529 346023955 468910473 125009381 361848882 337884709 446974381 436474372 415162784 15275340 316972404 331561910 410042584 415770232 152626645 41206655 472451077 92729488 96092722 193158556 237856703 203318642 347635859 54055213 174865002 466776930 326202945 55928087 432604664 402502274 214090956 196922281 211655317 146130517 321931662 36633287 484015227 232035132 473107659 362307099 247310472 253209152 156998098 120482144 132108472 309624744 161688799 67688638 402354232 257781521 260847194 103340024 461100164 71612141 157395238 99094254 1518160 483598183 155022342 434122824 349229546 369113298 94174194 24013951 515243816 416105857 60647238 462388132 111270077 533754898 287824319 358580549 250093138 444822418 479062693 382201611 217576250 103880581 449890249 83059570 361662103 173866531 186399595 285891355