commit ce2c687590e85b42b89a989eef2f23052b26535a parent 6b872565b3fd4fe1009147d503611224fc351446 Author: Shimmy Xu <shimmy.xu@shimmy1996.com> Date: Sat, 9 Dec 2023 16:27:46 -0500 Add 2023 day 09 Diffstat:
| A | 2023/day09/day09.scm | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/day09/input.txt | | | 200 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 251 insertions(+), 0 deletions(-) diff --git a/2023/day09/day09.scm b/2023/day09/day09.scm @@ -0,0 +1,51 @@ +(use-modules (ice-9 popen)) +(use-modules (ice-9 rdelim)) +(use-modules (ice-9 format)) +(use-modules (ice-9 receive)) +(use-modules (srfi srfi-1)) + +(define (parse-numbers numbers) + (filter (lambda (x) x) (map string->number (string-split numbers #\ )))) + +(define (parse-input filename) + (let ((file (open-input-file filename)) + (report '())) + (while #t + (let ((line (car (%read-line file)))) + (if (eof-object? line) + (break) + (set! report (cons (parse-numbers line) report))))) + (reverse report))) + +(define (all-zero history) + (if (null? history) + #t + (and (= (car history) 0) (all-zero (cdr history))))) + +(define (calc-diff history) + (if (< (length history) 2) + '() + (cons (- (car (cdr history)) (car history)) + (calc-diff (cdr history))))) + +(define (extrapolate history) + (if (all-zero history) + 0 + (+ (car (last-pair history)) (extrapolate (calc-diff history))))) + +(let* ((report (parse-input "input.txt")) + (extrapolated (map extrapolate report))) + ;; 1647269739 + (format #t "Part 1: ~d" (reduce + #nil extrapolated)) + (newline)) + +(define (backward-extrapolate history) + (if (all-zero history) + 0 + (- (car history) (backward-extrapolate (calc-diff history))))) + +(let* ((report (parse-input "input.txt")) + (extrapolated (map backward-extrapolate report))) + ;; 864 + (format #t "Part 2: ~d" (reduce + #nil extrapolated)) + (newline)) diff --git a/2023/day09/input.txt b/2023/day09/input.txt @@ -0,0 +1,200 @@ +-1 0 1 10 53 187 518 1233 2660 5388 10524 20246 38935 75343 146509 284568 548473 1044637 1965205 3663693 6812697 +12 30 67 142 300 622 1234 2331 4254 7687 14080 26460 50876 98851 191403 365471 683968 1251212 2236193 3907058 6681380 +6 21 49 109 241 526 1116 2268 4372 7959 13671 22171 33967 49120 66802 84666 97986 98521 73053 1545 -145139 +14 30 61 123 254 535 1128 2334 4674 8996 16611 29461 50322 83045 132838 206592 313254 464250 673961 960255 1345078 +7 25 59 119 215 357 555 819 1159 1585 2107 2735 3479 4349 5355 6507 7815 9289 10939 12775 14807 +-3 5 23 61 156 402 996 2298 4896 9665 17821 31006 51507 82820 130928 206879 331535 543725 913483 1562595 2695326 +29 52 96 185 369 754 1552 3169 6368 12582 24517 47280 90390 171174 320203 589568 1064911 1882184 3250078 5478907 9016407 +9 32 79 177 376 767 1525 2990 5803 11119 20923 38487 69054 120982 207967 353915 604314 1053295 1907636 3635070 7298141 +5 19 44 77 110 129 113 33 -149 -481 -1022 -1843 -3028 -4675 -6897 -9823 -13599 -18389 -24376 -31763 -40774 +17 35 61 99 164 303 630 1375 2947 6011 11579 21115 36654 60935 97548 151095 227365 333523 478313 672275 927976 +19 42 74 115 165 224 292 369 455 550 654 767 889 1020 1160 1309 1467 1634 1810 1995 2189 +-4 9 32 65 117 226 498 1183 2818 6479 14196 29597 58859 112056 205006 361731 617656 1023685 1651304 2598873 3999281 +11 30 76 163 305 516 810 1201 1703 2330 3096 4015 5101 6368 7830 9501 11395 13526 15908 18555 21481 +11 38 85 161 282 475 783 1280 2123 3711 7103 14982 33654 76854 172509 374095 778835 1555732 2987329 5530151 9900026 +3 14 35 66 107 158 219 290 371 462 563 674 795 926 1067 1218 1379 1550 1731 1922 2123 +0 12 30 52 76 100 122 140 152 156 150 132 100 52 -14 -100 -208 -340 -498 -684 -900 +1 7 24 70 180 421 916 1875 3624 6623 11496 19212 31843 54908 103352 214896 477035 1077563 2393352 5138342 10599366 +6 7 8 3 -6 -2 49 195 490 981 1690 2591 3582 4452 4843 4207 1758 -3581 -13236 -29045 -53326 +20 29 36 41 44 45 44 41 36 29 20 9 -4 -19 -36 -55 -76 -99 -124 -151 -180 +11 17 27 42 68 132 317 832 2136 5134 11452 23779 46268 85117 149956 258079 446901 807103 1562793 3250512 7093496 +-1 -5 -5 16 86 251 593 1278 2683 5694 12325 26885 58015 122009 247869 484450 909804 1642672 2857012 4805365 7872645 +14 21 49 116 250 504 984 1909 3747 7503 15270 31188 62985 124294 237947 440437 787708 1362377 2282407 3711132 5868380 +17 38 73 120 180 274 482 1021 2387 5607 12700 27567 57782 118236 238437 476716 947029 1868232 3653083 7067466 13514168 +7 16 24 39 73 139 247 399 583 766 886 843 489 -383 -2051 -4877 -9321 -15956 -25484 -38753 -56775 +-2 0 12 38 80 153 325 793 2000 4793 10633 21924 42691 80239 149336 282420 553382 1130634 2391186 5158118 11181006 +8 15 47 117 238 425 695 1069 1591 2398 3917 7368 15984 37821 91856 220419 513054 1149837 2476167 5126227 10218766 +-8 -6 -2 2 3 -2 4 125 711 2679 8104 21244 50242 109855 225700 440685 824514 1487424 2599634 4418366 7324741 +23 34 43 64 133 320 749 1628 3293 6277 11437 20244 35536 63480 118395 233784 485919 1041392 2248335 4804192 10053371 +18 37 81 170 340 654 1210 2152 3699 6212 10328 17219 29114 50418 90204 167776 324777 650472 1332004 2749185 5643949 +29 42 52 59 68 93 176 434 1157 3009 7440 17508 39444 85478 178688 360945 705413 1335532 2452972 4377705 7604108 +1 11 26 56 125 271 546 1016 1761 2875 4466 6656 9581 13391 18250 24336 31841 40971 51946 65000 80381 +5 2 13 65 200 470 927 1618 2611 4098 6643 11665 22266 44530 89429 175474 332241 604882 1059697 1790793 2927788 +10 26 62 131 259 496 941 1806 3557 7182 14657 29733 59284 115692 221208 416176 775068 1438887 2682669 5058399 9697151 +5 10 12 1 -39 -121 -236 -324 -235 320 1828 5043 11065 21429 38204 64102 102597 158054 235868 342613 486201 +17 35 59 93 145 244 486 1138 2844 6993 16326 35877 74362 146150 273971 492538 853283 1430431 2328661 3692629 5718655 +2 10 19 31 66 172 425 925 1818 3425 6657 14066 32158 76013 177863 402122 870498 1802308 3577031 6828545 12583482 +8 7 3 -4 -14 -27 -43 -62 -84 -109 -137 -168 -202 -239 -279 -322 -368 -417 -469 -524 -582 +17 30 59 130 290 616 1228 2322 4250 7685 13920 25361 46285 83945 150115 263179 450879 753848 1230065 1960380 3055268 +10 20 40 77 141 242 394 642 1146 2389 5633 13844 33483 77914 173951 374794 786430 1622761 3321496 6785708 13877601 +4 9 25 62 139 293 599 1213 2452 4940 9890 19676 38999 77204 152736 301499 592366 1156021 2239113 4306924 8238789 +1 10 32 73 139 236 370 547 773 1054 1396 1805 2287 2848 3494 4231 5065 6002 7048 8209 9491 +-1 9 28 51 78 129 264 608 1381 2933 5784 10669 18588 30861 49188 75714 113099 164593 234116 326343 446794 +7 16 25 34 43 52 61 70 79 88 97 106 115 124 133 142 151 160 169 178 187 +18 39 67 102 144 193 249 312 382 459 543 634 732 837 949 1068 1194 1327 1467 1614 1768 +19 33 58 94 136 176 213 289 586 1652 4884 13494 34331 81139 180109 378943 761101 1467459 2728278 4909182 8575778 +18 33 63 124 235 426 766 1433 2866 6067 13159 28354 59543 120788 236074 444767 809322 1425893 2438615 4058456 6587675 +20 44 92 175 306 510 843 1434 2571 4868 9588 19270 38929 78280 155693 304929 586150 1103252 2030252 3650281 6411708 +5 29 69 124 189 248 275 265 326 872 2966 8871 22876 52473 109970 214634 395467 694727 1172315 1911158 3023727 +-4 -8 -12 -16 -20 -24 -28 -32 -36 -40 -44 -48 -52 -56 -60 -64 -68 -72 -76 -80 -84 +15 34 57 94 173 345 690 1327 2435 4301 7428 12767 22191 39418 71729 133034 249135 466444 865963 1585052 2850433 +8 22 37 57 92 150 224 274 204 -166 -1133 -3149 -6864 -13174 -23274 -38716 -61472 -94002 -139327 -201107 -283724 +-1 -5 1 42 159 423 961 1994 3887 7211 12817 21922 36207 57927 90033 136306 201503 291515 413537 576250 790015 +20 42 86 159 268 420 622 881 1204 1598 2070 2627 3276 4024 4878 5845 6932 8146 9494 10983 12620 +26 44 71 120 221 427 820 1517 2676 4502 7253 11246 16863 24557 34858 48379 65822 87984 115763 150164 192305 +10 18 20 15 2 -6 58 390 1435 4064 9833 21403 43352 83965 159355 302878 586124 1164442 2372946 4923271 10295130 +20 45 95 180 302 451 601 706 696 473 -93 -1168 -2958 -5713 -9731 -15362 -23012 -33147 -46297 -63060 -84106 +-2 -7 -11 2 76 301 834 1921 3918 7309 12719 20920 32828 49489 72052 101727 139726 187185 245065 314030 394300 +14 36 77 152 301 606 1210 2338 4320 7616 12843 20804 32519 49258 72576 104350 146818 202620 274841 367056 483377 +2 8 27 77 181 366 662 1101 1716 2540 3605 4941 6575 8530 10824 13469 16470 19824 23519 27533 31833 +10 28 60 118 215 363 573 859 1248 1798 2626 3948 6133 9773 15771 25449 40678 64032 98968 150034 223107 +0 14 38 82 169 335 629 1113 1862 2964 4520 6644 9463 13117 17759 23555 30684 39338 49722 62054 76565 +-1 6 22 42 70 143 362 921 2125 4388 8206 14130 22871 35954 57996 103088 210615 481422 1155734 2773334 6490064 +7 1 2 27 108 298 680 1387 2644 4846 8691 15396 27039 47093 81251 138686 233949 389783 641224 1041473 1670158 +-4 4 22 50 94 189 444 1126 2815 6685 15010 32090 66003 132044 259673 506768 988886 1938642 3823746 7575562 15018972 +4 9 20 30 31 11 -52 -202 -532 -1240 -2718 -5619 -10667 -17536 -21176 -2062 96807 420142 1304283 3483711 8488810 +10 9 5 -6 -33 -90 -196 -375 -656 -1073 -1665 -2476 -3555 -4956 -6738 -8965 -11706 -15035 -19031 -23778 -29365 +9 21 48 107 233 490 982 1864 3353 5739 9396 14793 22505 33224 47770 67102 92329 124721 165720 216951 280233 +11 23 45 99 230 516 1078 2104 3914 7116 12946 23958 45343 87319 169257 326501 621213 1159037 2113939 3764253 6543756 +15 43 97 191 355 658 1254 2463 4901 9680 18712 35169 64172 113816 196741 332797 554303 917709 1530451 2611603 4622933 +23 44 70 101 153 285 654 1626 3994 9391 21042 45079 92752 184012 353124 657194 1188769 2093998 3598230 6041377 9925891 +11 22 41 64 79 77 92 299 1216 4075 11448 28237 63162 130908 255121 472474 838057 1432380 2370315 3812342 5978505 +12 20 39 69 110 162 225 299 384 480 587 705 834 974 1125 1287 1460 1644 1839 2045 2262 +-4 -7 -7 11 85 292 770 1756 3669 7307 14305 28153 56377 115093 238307 496430 1032034 2126660 4321812 8632855 16922647 +14 33 63 119 241 519 1137 2460 5205 10760 21747 42978 83066 157220 292371 537135 981979 1800811 3337066 6281357 12036590 +11 9 6 5 22 100 323 830 1829 3611 6564 11187 18104 28078 42025 61028 86351 119453 162002 215889 283242 +-6 7 38 89 157 238 352 616 1403 3647 9406 22910 52561 114825 241831 496024 997830 1976808 3864994 7467070 14274023 +11 27 46 69 113 224 490 1054 2127 4001 7062 11803 18837 28910 42914 61900 87091 119895 161918 214977 281113 +8 21 60 140 282 519 912 1595 2890 5571 11429 24432 53034 114629 243849 507463 1030156 2037577 3925882 7370716 13493346 +19 37 64 110 197 359 642 1104 1815 2857 4324 6322 8969 12395 16742 22164 28827 36909 46600 58102 71629 +8 25 56 112 218 425 831 1618 3109 5841 10650 18813 32481 56135 100884 195528 412046 919385 2089240 4692362 10245604 +24 30 41 63 98 149 232 403 823 1913 4711 11658 28236 66181 149413 324365 677038 1359820 2631817 4917053 8885266 +-1 1 11 36 91 205 428 843 1587 2885 5101 8810 14895 24673 40054 63737 99447 152217 228719 337648 490163 +22 33 54 105 219 441 835 1515 2728 5034 9650 19052 37961 74876 144359 270324 490634 863367 1475174 2452219 3974263 +12 24 52 116 259 557 1133 2187 4072 7473 13785 25847 49288 94899 182687 348621 655576 1210650 2191902 3888666 6760965 +10 20 39 87 195 405 770 1354 2232 3490 5225 7545 10569 14427 19260 25220 32470 41184 51547 63755 78015 +9 4 -1 -6 -11 -16 -21 -26 -31 -36 -41 -46 -51 -56 -61 -66 -71 -76 -81 -86 -91 +14 28 69 165 368 770 1524 2870 5166 8924 14851 23895 37296 56642 83930 121632 172766 240972 330593 446761 595488 +-3 -5 -4 19 93 254 542 998 1661 2565 3736 5189 6925 8928 11162 13568 16061 18527 20820 22759 24125 +22 35 56 99 198 416 854 1660 3038 5257 8660 13673 20814 30702 44066 61754 84742 114143 151216 197375 254198 +19 40 66 95 125 170 290 647 1612 3971 9324 20856 44814 93323 189797 379566 751353 1481722 2928018 5821733 11663931 +4 9 12 5 -13 -18 61 375 1224 3213 7580 16823 35803 73558 146129 280773 522020 940121 1642532 2789185 4612411 +-4 6 21 50 111 231 449 817 1405 2351 4064 7792 16909 39451 92631 210270 454270 931392 1816643 3384466 6048599 +0 12 45 115 257 531 1032 1920 3489 6294 11354 20449 36532 64285 110863 186894 307838 495856 782403 1211839 1846451 +25 49 97 186 338 574 916 1417 2247 3881 7473 15571 33454 71593 150126 306925 612082 1193986 2286702 4317281 8069083 +2 -3 -7 2 50 187 509 1207 2676 5745 12129 25265 51794 104114 204677 393043 737110 1350329 2416921 4226856 7221194 +26 53 104 203 395 760 1439 2679 4922 9006 16625 31320 60454 118890 235539 464828 906996 1744958 3312949 6225851 11621821 +8 29 73 162 327 616 1125 2063 3866 7388 14221 27230 51430 95378 173308 308326 537203 917975 1543562 2570100 4282344 +7 9 23 67 179 430 942 1915 3670 6718 11868 20390 34252 56453 91477 145896 229153 354559 540541 812181 1203089 +15 28 52 89 137 190 238 267 259 192 40 -227 -643 -1246 -2078 -3185 -4617 -6428 -8676 -11423 -14735 +11 32 67 126 235 458 931 1914 3879 7670 14803 28030 52388 97142 179466 331825 617918 1169203 2270654 4560657 9484528 +7 14 30 63 125 232 404 665 1043 1570 2282 3219 4425 5948 7840 10157 12959 16310 20278 24935 30357 +1 -2 9 60 205 550 1289 2751 5455 10180 18085 30959 51745 85594 141957 238817 411473 730950 1342165 2541118 4926337 +26 43 79 149 276 500 893 1598 2926 5558 10904 21665 42628 81705 151220 269478 462754 768069 1237541 1945797 3003012 +15 28 45 66 96 159 331 800 1961 4554 9853 19914 37890 68421 118107 196072 314627 490040 743421 1101730 1598916 +10 30 65 136 278 540 985 1690 2746 4258 6345 9140 12790 17456 23313 30550 39370 49990 62641 77568 95030 +2 0 -4 5 59 206 516 1118 2314 4862 10607 23795 53689 119642 260821 554822 1153485 2352343 4726289 9395692 18547838 +-2 1 17 64 170 372 721 1296 2238 3828 6650 11911 22063 42040 81771 161282 320826 640303 1275035 2519094 4913268 +-1 -4 -7 -10 -13 -16 -19 -22 -25 -28 -31 -34 -37 -40 -43 -46 -49 -52 -55 -58 -61 +7 19 39 67 103 147 199 259 327 403 487 579 679 787 903 1027 1159 1299 1447 1603 1767 +3 11 19 27 35 43 51 59 67 75 83 91 99 107 115 123 131 139 147 155 163 +22 45 72 95 111 145 299 838 2324 5809 13098 27093 52229 95013 164677 273956 440002 685445 1039612 1539915 2233419 +18 44 94 191 368 666 1132 1817 2774 4056 5714 7795 10340 13382 16944 21037 25658 30788 36390 42407 48760 +14 35 73 149 302 601 1158 2154 3916 7133 13384 26289 53819 112677 236320 489421 994006 1977471 3862775 7441041 14204720 +14 15 29 71 156 299 515 819 1226 1751 2409 3215 4184 5331 6671 8219 9990 11999 14261 16791 19604 +12 23 31 47 102 268 694 1665 3700 7713 15269 28975 53054 94158 162484 273265 448716 720523 1132971 1746815 2644006 +10 30 70 158 340 695 1362 2577 4717 8352 14322 23911 39354 65338 113153 211334 431251 945601 2156837 4969935 11355019 +23 38 71 139 261 458 753 1171 1739 2486 3443 4643 6121 7914 10061 12603 15583 19046 23039 27611 32813 +19 35 63 103 155 219 295 383 483 595 719 855 1003 1163 1335 1519 1715 1923 2143 2375 2619 +6 17 54 137 295 566 997 1644 2572 3855 5576 7827 10709 14332 18815 24286 30882 38749 48042 58925 71571 +12 22 32 42 52 62 72 82 92 102 112 122 132 142 152 162 172 182 192 202 212 +13 17 30 69 165 372 780 1537 2902 5386 10103 19565 39335 81225 169122 349081 706087 1390919 2661928 4948373 8944381 +5 0 -8 -10 10 86 309 921 2516 6433 15461 35015 75005 152755 297622 558550 1016863 1808414 3162102 5466172 9380148 +27 43 75 138 261 503 977 1891 3625 6887 13034 24708 47028 89719 170803 322935 604331 1117811 2044225 3701094 6644571 +12 12 13 27 75 185 390 726 1230 1938 2883 4093 5589 7383 9476 11856 14496 17352 20361 23439 26479 +4 10 15 23 43 89 177 315 477 548 231 -1072 -4344 -10851 -21557 -35540 -46582 -36682 35319 252533 769681 +19 33 68 134 238 394 658 1209 2518 5694 13182 30138 67067 144763 303377 618841 1232525 2405394 4619522 8775207 16586824 +10 30 64 132 260 488 891 1613 2927 5370 10071 19502 39047 80012 165000 336959 673688 1310166 2471762 4522200 8031102 +9 22 51 107 215 433 893 1886 4030 8589 18054 37153 74522 145336 275258 506102 903607 1567664 2645205 4345727 6959057 +24 36 63 127 260 516 987 1821 3245 5607 9483 15973 27469 49473 94578 190710 397574 838702 1762851 3659823 7475282 +17 25 24 6 -29 -57 3 353 1441 4213 10635 24787 55140 119198 252716 527563 1085727 2203455 4412052 8726090 17076047 +-2 10 33 77 159 305 574 1122 2327 4999 10702 22218 44186 83952 152669 266689 449292 732800 1161127 1792819 2704641 +16 16 7 -1 22 138 469 1251 2929 6315 12847 25034 47291 87632 161247 298189 560079 1076855 2128429 4326525 9016295 +4 19 46 90 155 246 378 592 985 1776 3450 7040 14612 29995 59728 114056 207570 358721 586910 905126 1305129 +13 25 37 49 61 73 85 97 109 121 133 145 157 169 181 193 205 217 229 241 253 +21 29 47 94 200 402 738 1245 1968 2985 4452 6680 10285 16518 28005 50331 95215 186477 370629 734770 1435574 +5 3 4 28 115 338 822 1770 3493 6433 11157 18294 28418 42041 60388 88923 148512 305135 740775 1909866 4864592 +19 26 45 85 151 249 409 743 1555 3524 7997 17468 36407 72801 141201 268958 509043 965942 1846413 3555527 6871927 +14 35 68 114 185 319 595 1153 2226 4185 7581 13145 21702 34023 50882 74184 111318 187508 376143 867288 2114317 +7 18 37 71 149 343 796 1757 3623 6988 12699 21919 36197 57545 88522 132325 192887 274982 384337 527751 713221 +3 0 -3 3 46 193 579 1448 3211 6528 12423 22443 38874 65029 105625 167268 259067 393400 586857 861387 1245678 +-7 -12 -11 11 84 260 620 1281 2403 4196 6927 10927 16598 24420 34958 48869 66909 89940 118937 154995 199336 +8 12 35 93 215 446 856 1561 2764 4844 8569 15592 29505 57854 115604 230482 450240 850892 1542983 2669375 4382115 +22 34 56 95 164 286 507 932 1814 3751 8080 17599 37792 78779 158327 306707 575727 1058706 1939267 3612055 6971685 +21 29 54 108 215 427 848 1669 3210 5950 10503 17469 27070 38538 49546 57012 63284 97800 277073 951199 3033702 +2 7 14 18 11 -11 -24 74 551 1983 5471 12960 27694 54849 102395 182248 311784 515799 829012 1299222 1991245 +7 8 14 37 109 290 683 1462 2916 5509 9953 17288 28960 46885 73484 111671 164773 236358 329944 448559 594119 +16 31 45 70 133 276 556 1045 1830 3013 4711 7056 10195 14290 19518 26071 34156 43995 55825 69898 86481 +1 14 47 102 183 310 546 1052 2205 4850 10815 23904 51703 108694 221378 436366 832713 1540150 2765319 4828642 8215063 +11 20 32 51 76 110 194 481 1370 3731 9280 21231 45498 93013 184316 358805 693665 1343062 2619584 5162235 10277044 +14 22 34 63 145 353 811 1708 3312 5984 10192 16525 25707 38611 56273 79906 110914 150906 201710 265387 344245 +0 15 40 77 148 315 710 1580 3361 6811 13249 24956 45791 82090 144077 248662 426358 739483 1328174 2518811 5062014 +13 24 45 82 152 302 631 1324 2717 5422 10551 20088 37468 68432 122237 213310 363445 604652 982777 1562022 2430504 +19 35 60 106 190 334 565 915 1421 2125 3074 4320 5920 7936 10435 13489 17175 21575 26776 32870 39954 +-5 -3 10 48 133 308 665 1391 2834 5584 10548 18969 32292 51709 77113 105050 125069 113623 24358 -226770 -783601 +6 20 57 127 243 434 773 1428 2760 5528 11333 23577 49500 104426 220466 464098 971182 2015628 4141645 8413187 16873749 +7 21 39 70 131 249 473 917 1876 4085 9224 20808 45638 96025 193032 371007 683701 1212277 2075517 3442522 5548173 +13 18 42 98 210 431 867 1700 3196 5673 9385 14259 19439 22737 20581 10357 151 37736 284768 1189736 3864504 +7 25 64 144 306 634 1298 2626 5217 10120 19135 35356 64194 115317 206257 368900 660739 1183683 2114434 3752032 6590194 +7 14 21 28 35 42 49 56 63 70 77 84 91 98 105 112 119 126 133 140 147 +-4 0 9 27 77 222 599 1472 3314 6940 13744 26162 48617 89436 164606 304807 567984 1060864 1974363 3639845 6615781 +11 36 73 119 171 226 281 333 379 416 441 451 443 414 361 281 171 28 -151 -369 -629 +10 16 23 31 40 50 61 73 86 100 115 131 148 166 185 205 226 248 271 295 320 +21 30 53 115 257 543 1070 1981 3481 5856 9495 14915 22789 33977 49560 70877 99565 137602 187353 251619 333689 +19 28 45 78 139 250 458 867 1712 3530 7527 16299 35140 74262 152362 302100 578201 1069064 1912953 3320060 5601969 +-1 14 43 102 220 432 780 1340 2295 4077 7620 14837 29624 60111 123683 257703 541175 1136160 2363065 4831528 9659196 +-1 -5 -9 -13 -17 -21 -25 -29 -33 -37 -41 -45 -49 -53 -57 -61 -65 -69 -73 -77 -81 +11 28 63 118 201 335 563 959 1666 2991 5602 10917 21906 44869 93573 198969 431604 951705 2117140 4707907 10377258 +14 25 48 87 144 223 341 545 940 1750 3462 7142 15062 31838 66351 134806 265378 504999 928956 1654097 2856580 +14 24 46 85 143 226 365 658 1340 2885 6145 12563 24622 47029 89899 176796 363638 780518 1719812 3814625 8388429 +4 19 47 104 217 424 774 1327 2154 3337 4969 7154 10007 13654 18232 23889 30784 39087 48979 60652 74309 +-5 -8 0 43 170 465 1057 2139 4010 7153 12366 21003 35514 60783 107372 198848 387105 782250 1607512 3295127 6646686 +21 45 95 184 318 486 645 708 562 174 -111 1094 7549 27958 80971 205196 479799 1067457 2303625 4879164 10205648 +15 21 43 89 174 340 702 1543 3489 7803 16845 34753 68408 128754 232552 404655 680899 1111713 1766559 2739321 4154770 +18 32 58 115 227 417 710 1172 2032 3960 8606 19543 43801 94229 192978 376460 702206 1258120 2174706 3640931 5924479 +7 28 54 84 133 243 494 1017 2026 3921 7573 14987 30650 64006 133655 274042 545577 1049298 1947344 3490630 6055195 +24 42 81 152 274 485 867 1606 3115 6253 12672 25309 49010 91262 163146 281256 473274 794968 1378521 2559628 5190918 +27 45 66 91 134 234 467 958 1893 3531 6216 10389 16600 25520 37953 54848 77311 106617 144222 191775 251130 +7 18 33 62 139 331 747 1547 2951 5248 8805 14076 21611 32065 46207 64929 89255 120350 159529 208266 268203 +0 -4 -3 13 72 231 585 1274 2488 4470 7517 11979 18256 26793 38073 52608 70928 93568 121053 153881 192504 +0 2 10 44 141 360 781 1505 2679 4587 7871 13991 26125 50882 101493 203603 405462 795260 1529628 2878994 5297601 +7 22 59 127 235 391 605 905 1375 2224 3895 7223 13651 25513 46393 81569 138551 227722 363091 563167 851963 +14 25 35 44 52 59 65 70 74 77 79 80 80 79 77 74 70 65 59 52 44 +3 13 38 100 235 492 943 1733 3217 6250 12715 26403 54434 109616 214659 410338 772197 1445522 2718764 5176819 10018447 +17 41 87 172 327 601 1077 1921 3493 6564 12718 25103 49886 99152 196689 389278 767949 1506387 2927509 5614422 10588741 +6 18 38 86 195 411 793 1413 2356 3720 5616 8168 11513 15801 21195 27871 36018 45838 57546 71370 87551 +16 28 40 52 64 76 88 100 112 124 136 148 160 172 184 196 208 220 232 244 256 +14 26 45 76 133 239 426 735 1216 1928 2939 4326 6175 8581 11648 15489 20226 25990 32921 41168 50889 +23 52 110 207 361 609 1016 1696 2873 5024 9160 17315 33327 64009 120822 222176 396499 686228 1152890 1883455 2998157 +24 47 86 147 236 359 522 731 992 1311 1694 2147 2676 3287 3986 4779 5672 6671 7782 9011 10364 +9 6 -5 -17 -11 44 191 485 993 1794 2979 4651 6925 9928 13799 18689 24761 32190 41163 51879 64549 +7 24 52 109 234 502 1045 2077 3921 7034 12019 19594 30453 44918 62303 80128 93991 100460 108450 170171 452224 +12 24 51 103 198 376 728 1454 2973 6124 12520 25147 49337 94288 175355 317394 559506 961600 1613273 2645591 4246448 +-4 -4 6 31 81 172 336 667 1438 3335 7885 18247 40765 88185 186457 389026 806276 1664738 3423116 6993687 14153381 +7 21 49 103 213 442 904 1788 3410 6344 11732 21974 42209 83403 168586 345017 707101 1438207 2884887 5685529 10988937 +9 31 64 108 162 224 297 419 750 1764 4609 11713 27729 60927 125156 242514 446879 788469 1339614 2201938 3515164 +19 45 90 166 301 551 1022 1914 3615 6915 13504 27104 55917 117617 248956 523288 1081051 2180609 4279982 8164034 15136813 +8 27 72 156 292 493 772 1142 1616 2207 2928 3792 4812 6001 7372 8938 10712 12707 14936 17412 20148 +18 41 93 203 409 756 1297 2097 3240 4839 7049 10083 14231 19882 27549 37897 51774 70245 94629 126539 167925 +7 16 39 75 122 192 349 791 2020 5181 12702 29432 64553 134635 268310 513162 945565 1684350 2909345 4886009 7997572 +2 17 50 122 277 595 1210 2349 4421 8195 15123 27909 51530 95123 175517 323776 597004 1098933 2014568 3666508 6603619