1000
71984986 118550129 290674464 252446328 195781941 62142589 47046893 298769805 186815488 24305670 239836193 305898215 3382590 184683224 276577207 289474730 75685458 138027600 280673485 236440782 1789014 262431297 299122840 182981567 233127303 179639536 206456142 6066941 196906375 205046264 305108299 238559581 63762730 217773223 522477 304382373 262506713 209559678 121947575 70942003 53111299 219449237 41057874 132136231 72586439 309690981 74510391 165978437 6488363 254578940 322959958 282595861 233997032 253260973 206531378 119185106 236655323 45602414 7108851 269777502 325153606 34373768 157970786 151465564 130253725 155332554 246779569 171489316 83743465 98361957 25201345 2998179 318820424 225518097 132473353 178775480 267025739 235827944 237870214 121221305 261990615 164924326 173624534 145488588 235155477 115135263 125597995 227099070 90764690 26187784 209601854 120645440 121979440 142578221 88633449 175421012 156975107 210814218 269711500 225551140 56954036 28750450 164421433 159536172 254952177 35517131 123008873 203305963 42070043 304154543 232308693 260771654 154182007 230719117 138006700 278896677 156888846 230085078 218292420 325579492 131498445 196298721 177119585 53353411 107724389 297301015 299948192 170285206 193182092 172474535 128938719 19243750 88043882 137069795 128155761 113728510 279485021 133902066 113134287 126955759 327678054 36625900 14870386 198769724 141890410 321983985 29814027 317368687 314753553 161000482 154962459 69661554 203314938 139243606 92072859 71153223 311242582 102432694 175563301 159743809 124283512 319952370 47744217 252083896 246752076 68072714 324040329 257810265 318742732 185922245 39498605 34884867 251431020 102080750 34270079 40796604 192583920 145024290 154333232 59279562 205089633 290000691 97565074 261329594 314534443 257615512 300728876 13387532 269693458 308634651 246096218 3600565 327290120 113738506 85662906 149014716 111389608 285773846 12887519 165006734 135336543 20716167 2594450 176011370 87980414 22333141 247562332 56274229 109690409 225210705 325347421 122260630 143365195 179965770 44170840 227863259 309628080 134811128 2425685 210882611 11986681 192107429 222852462 53263906 32260747 161161807 138416082 81882961 79322784 107301447 257736101 227575755 311035765 286638709 266740830 307815265 275715786 138617346 120409159 23126455 188279670 268871356 192760545 304729604 281270272 212926630 156716718 115864118 196923351 173282453 198767716 175386651 58407227 175885188 308716705 168527577 271523377 250445825 265463122 258724535 56487059 324370158 319421226 18634322 280650558 157412833 277014833 23897402 106107538 300470180 265250658 210820754 231855110 145994149 225705708 241202275 279001281 279453335 105570514 235727353 148584146 284181712 89115788 237725925 110066457 191475705 215080003 45440009 275126843 5839425 34868088 68273423 112677042 254032698 277866126 258195811 298348538 281383418 297811004 64702244 17555222 193647611 147670540 69575447 207819289 218211676 74109631 57766355 288192717 106305102 52679190 78684534 172937968 214643671 19671562 237338623 31899345 6595907 144774261 199134946 92369128 198593390 161427591 46265528 153785419 32600939 49275954 191697212 126639866 159943424 101876430 23863407 284667540 323164759 52527205 196485236 247310079 27942911 207049880 44373173 296730996 239401993 323760553 282735308 114425937 203425020 172921391 177328251 180452790 208090802 136880534 325700821 264061832 125319352 213215692 236837602 249564032 287988673 41329476 211449135 19606621 113810500 281210119 314135355 35101278 47022057 100741598 41866747 317752809 264477680 274463177 327087672 128550615 77702154 97744332 11474012 309098325 325396062 239664172 224803000 92938997 235954550 66636262 284891376 184132939 229535327 249724536 192632781 305948337 173435005 170211846 218271339 67481731 299727604 280954695 201514473 198782371 197937392 249416582 202739148 222660886 142509422 90122625 212768412 99260757 167233952 28048333 230655828 273726253 163897950 74663488 55239142 125894864 21727695 300664197 100432277 65671281 135608484 166632652 285477818 65030172 316798190 188196296 276817200 196710044 55296850 37759167 98732456 231070371 133921196 291848637 129429061 257018566 23640729 286994945 155180337 32783150 234658300 276589518 103766790 16637224 121500986 24121003 163404870 144222597 316101630 58861780 287522804 285664843 287001302 23474951 68025848 88064995 198987332 11457976 287860943 169801721 192663965 307433390 254772920 78838447 32331357 185193395 91318424 224372025 105625042 23480472 116597543 244686978 170535261 186108462 268872081 37665126 109251860 270480302 224753687 176789095 67619666 35640066 214475851 74175224 308070949 43577194 239806391 117131877 120236223 47685656 316045942 240848841 49496598 43573604 99380329 180508917 234195540 50341801 194041092 92101056 94714952 260205926 223062207 231266738 29281283 246189358 217213270 17467464 201995339 176913048 78736553 88486563 26930427 106170959 68820700 135847641 314622673 286517059 25782583 58201810 216801199 213031719 262169191 172449868 110204940 2077969 209231068 155232183 261501632 172172254 51671770 319069066 188653899 155548875 109145656 308036077 29113662 127212780 259185539 128208124 310810879 253500057 56156972 235851898 125574458 309525516 201887478 28433692 258680875 320217540 125438409 308628330 133503285 259834933 190851298 218608578 40093871 119507190 14089600 113760565 127695601 16225698 97481544 217295847 93717243 14851575 228645602 299025027 224471614 318815690 213667690 50501844 182938785 191148529 324070368 156107309 131278686 193185639 145868233 128921363 256096338 204289084 91472540 119032430 6707120 104237683 2922021 141956204 323661887 168696658 90524005 2957229 10017031 195017765 273247888 245602039 7625656 307168827 216057838 192057236 178202436 163708663 63364906 284182512 56997440 172246513 230315782 205799691 303178119 123892386 252115861 322699485 258837926 162004684 295636192 214523181 136515425 153928735 90724738 196539288 298488332 86315381 196024284 261264497 249601891 174112168 29179121 43762971 292024499 27080118 197490074 138819968 272402575 151443124 282525988 182227630 7929916 215328439 269671405 249821253 81296917 304497661 52776875 3726042 55086424 252919250 290668037 173326039 3892838 325027707 27333672 144946296 121381703 300483215 251904051 180175536 40659764 238321769 290102715 70576514 161574443 299108552 135193640 127114104 69929327 280165183 198506118 244481088 274430133 175145125 117580742 317028889 52525624 118702518 226896938 40515403 252193462 45054080 120652060 65212844 236707617 42258903 205082199 241213772 112984111 92499169 15535004 198057130 52052154 180965818 178526991 293445228 305620848 117755314 155253480 308672443 280581908 56429034 285544098 151547621 276091164 70251003 268779215 272357577 312238401 97114399 306665330 154600014 310659826 253271317 321291396 123789053 315901633 204729169 197097312 247917410 102401284 218173098 63580758 261847983 133335877 286781643 291642188 188179753 266494387 279856274 219878152 15955866 139527615 133632484 198697879 75643885 251531392 83004119 71138634 144608676 136530255 278686055 315712180 231441477 182467147 117899489 281428333 91126505 213930374 237150043 68012385 91492060 82572567 286526778 153531314 154577648 297969670 21431258 79689394 49852650 78170419 107612618 127495370 55981635 28830127 18352494 84503494 25077384 275661121 232011675 19338886 126419931 276210882 211017694 113896766 320327776 311133442 26110741 209000471 200840656 67181249 55643908 46324412 189785113 210361990 70320066 206581982 150756524 67853116 325021993 139720545 9657326 266062384 70190218 168003693 88946168 166772276 36392406 253388893 171989239 259569807 44314486 116634547 246582700 7362523 260764836 52584754 306700509 320960341 201296368 148230099 194980579 175736977 67876764 196654001 141604186 151006131 161539200 307925532 33456931 111814951 7800327 249709498 34930805 208730106 145195792 139808065 266516728 280080511 21923646 196520110 196984185 278082219 193826984 202335506 42384729 80754873 303152154 319325423 239824894 148630 47598514 307034816 307151728 20634966 190076532 92098142 37142205 61290717 5306806 51120043 77254806 279401991 9961893 23710955 256866496 103962562 146314142 5172582 248834195 259282126 300726789 224315096 272311646 242232276 207577218 279650802 198020145 100202939 49550703 282398902 5152530 283742708 116065707 74286910 279468713 229657936 174496442 125042981 130455716 261903397 193651891 176662748 65166932 256445741 124750401 222728775 315196957 313316806 51227523 217849421 187611370 158760803 51731564 155662652 78533591 226953050 104132387 187968627 250701157 161060884 30525155 129314470 307331401 304475056 138500092 313306749 17804221 283770528 265011648 196242741 184133182 254257130 171687080 278124494 271792013 220195784 309331485 133094891 13392830 51551816 1356271 84667141 70656364 196799373 255973009 300925192 115536674 143268461 65857771 258122485 229284659 194902017 285081031 211445023 48763108 14402840 10665732 85243854 247320093 155480996 213898150 42638030 124596683 31304028 203718611 112972512 152424065 184098088 29246088 188143160 301863906 7914648 301921570 59456222 49671977 100081517 92400854 151367054 63925633 66003278 111373338 1830568 326385629 296992196 33108537 60982609 261752866 184736846 119712003 253451359 218541783 308771214 265041098 220428609 42059148 77542587 62549110 257870421 309361792 325392237 224722610 1928287 1126362 52471508 111412061 104412457 112479089 86910065 214445674 17307885 95884355 233969723 95389904 77661917 243125426 71267500 296630427 29247356 176392275 112053169 33617433 206716019 1261133 60769438 170759262 138887852 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4 
4