[解题报告][NFLSOJ529][2020六校联合训练省选2]打卡任务

BruceW 收录于 OI 解题报告

2021-03-04 约 6900 字预计阅读 14 分钟

Statement

传送门

$0 \le k < n < 998244353, 1 \le m \le n$。

Solution

先把答案用二元生成函数的形式表示出来，即

$$ \mathrm{ans} = [y^m][x^k] \prod_{i = 0}^{n - 1} (1 - x^iy) \pmod{(x^n - 1)} $$

（$ \mod{(x^n - 1)} $即为循环卷积。）

然后由于 $x$ 这一维是循环卷积，所以我们考虑引入单位根，用 DFT、IDFT 的形式来表示答案。

回顾一下 IDFT 的过程。设 $A$ 为多项式，向量 $B$ 为 $A$ 在 $\omega_{n}^{0 \sim n - 1}$ 处的点集，则有

$$ \frac{1}{n} \begin{Bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_{n}^{1} & \omega_{n}^{2} & \cdots & \omega_{n}^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{n}^{k} & \omega_{n}^{2k} & \cdots & \omega_{n}^{(n - 1)k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{n}^{n - 1} & \omega_{n}^{2(n-1)} & \cdots & \omega_{n}^{(n - 1)(n - 1)} \\ \end{Bmatrix} B = A $$

现在 $B$ 是容易用单位根表示的，那么 $A$ 的 $k$ 次项系数就也可以用单位根来表示，即

$$ \begin{aligned} \mathrm{ans} &= [y^m][x^k] \prod_{i = 0}^{n - 1} (1 - x^iy) \pmod{(x^n - 1)} \\ &= [y^m]\frac{1}{n}\sum_{j = 0}^{n - 1} \omega_{n}^{-jk} \prod_{i=0}^{n-1}(1+\omega_{n}^{ij}y) \end{aligned} $$

后面 $\prod_{i=0}^{n-1}(1+\omega_{n}^{ij}y)$ 这就是将 $n$ 次单位根中的若干个的若干次方乘了起来。那么我们可以考虑直接找出是哪几个单位根被算进了贡献里，然后将原来的式子用这几个单位根的若干次方表示，这样相当于减少了要考虑的因素。

具体来说，设 $d = \gcd(n, j)$，则被算进贡献里的单位根就只有 $\omega_{n}^{0}, \omega_{n}^{d}, \omega_{n}^{2d}, \cdots, \omega_{n}^{n - d}$ 这 $\frac{n}{d}$ 项，并且每一项都贡献了 $d$ 次方。

即 $\prod_{i=0}^{n-1}(1+\omega_{n}^{ij}y) = \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d}$。

我们发现转化后的式子至于 $d$ 有关，所以我们可以考虑先枚举 $d$，然后再莫比乌斯反演一下，即

$$ \begin{aligned} \mathrm{ans} &= [y^m]\frac{1}{n}\sum_{j = 0}^{n - 1} \omega_{n}^{-jk} \prod_{i=0}^{n-1}(1+\omega_{n}^{ij}y) \\ &= [y^m]\frac{1}{n}\sum_{j = 0}^{n - 1} \omega_{n}^{-jk} \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \\ &= [y^m]\frac{1}{n} \sum_{d | n} \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \sum_{j = 0}^{n - 1} [\gcd(n, j) == d]\omega_{n}^{-jk} \\ &= [y^m]\frac{1}{n} \sum_{d | n} \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \sum_{j = 0}^{\frac{n}{d} - 1} [\gcd(\frac{n}{d}, j) == 1]\omega_{n}^{-jk} \\ \end{aligned} $$

然后我们把后面 $\sum_{j = 0}^{\frac{n}{d} - 1} [\gcd(\frac{n}{d}, j) == 1]\omega_{n}^{-jk}$ 单独拿出来莫比乌斯反演一下，可以得到

$$ \sum_{j = 0}^{\frac{n}{d} - 1} [\gcd(\frac{n}{d}, j) == 1]\omega_{n}^{-jk} = \sum_{e | \frac{n}{d}} \mu(e) \sum_{j = 0}^{\frac{n}{de} - 1} \omega_{\frac{n}{de}}^{-jk} $$

然后发现 $\sum_{j = 0}^{\frac{n}{de} - 1} \omega_{\frac{n}{de}}^{-jk}$ 这一坨式子长的是个单位根反演的形式，所以我们可以反向使用单位根反演，即

$$ \begin{aligned} \sum_{j = 0}^{\frac{n}{d} - 1} [\gcd(\frac{n}{d}, j) == 1]\omega_{n}^{-jk} &= \sum_{e | \frac{n}{d}} \mu(e) \sum_{j = 0}^{\frac{n}{de} - 1} \omega_{\frac{n}{de}}^{-jk} \\ &= \sum_{e | \frac{n}{d}} \mu(e) \sum_{j = 0}^{\frac{n}{de} - 1} \omega_{\frac{n}{de}}^{jk} \\ &= \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \\ \end{aligned} $$

所以答案计算式可以化为

$$ \begin{aligned} \mathrm{ans} &= [y^m]\frac{1}{n} \sum_{d | n} \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \sum_{j = 0}^{\frac{n}{d} - 1} [\gcd(\frac{n}{d}, j) == 1]\omega_{n}^{-jk} \\ &= [y^m]\frac{1}{n} \sum_{d | n} \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \\ &= \frac{1}{n} \sum_{d | n} \left( \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \right)\left( [y^m] \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \right) \\ \end{aligned} $$

现在我们就是要求 $\prod_{i = 0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^d$ 这个多项式的 $m$ 次项系数。

我们设 $H(y) = \prod_{i = 0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)$。（和上面那个式子相比少了一个 $d$ 次方。）

由于 $H(y)$ 现在是个乘积的形式，所以方程 $H(y) = 0$ 的解集我们容易得到，即为 $-\omega_{\frac{n}{d}}^{0 \sim \frac{n}{d} - 1}$。

然后对于两个多项式 $A(x), B(x)$，若它们的解集相同，并且常数项相等，那么我们可以判定 $A$ 和 $B$ 是相等的。

我们考虑多项式 $A(y) = y^n - 1$，显然它的解集为 $\omega_{n}^{0 \sim n - 1}$。而多项式 $H(y)$ 的解集为 $-\omega_{\frac{n}{d}}^{0 \sim \frac{n}{d} - 1}$。

那么我们稍微构造一下，就可以得到一个多项式 $B(y) = 1 + (-1)^{\frac{n}{d} - 1}y^{\frac{n}{d}}$，它的解集就为 $\omega_{\frac{n}{d}}^{0 \sim \frac{n}{d} - 1}$。

然后 $H(y)$ 和 $B(y)$ 的常数项都为 $1$，所以我们有 $H(y) = B(y)$。

那么答案的计算式可以进一步化为

$$ \begin{aligned} \mathrm{ans} &= \frac{1}{n} \sum_{d | n} \left( \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \right)\left( [y^m] \prod_{i=0}^{\frac{n}{d} - 1} (1 + \omega_{\frac{n}{d}}^{i}y)^{d} \right) \\ &= \frac{1}{n} \sum_{d | n} \left( \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \right)\left( [y^m] (1 + (-1)^{\frac{n}{d} - 1}y^{\frac{n}{d}})^d \right) \\ &= \frac{1}{n} \sum_{d | n} \left( \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \right)\left( [y^m] \sum_{i = 0}^{\frac{n}{d}} \binom{d}{i} y^{\frac{n}{d}i} (-1)^{(\frac{n}{d} - 1)i} \right) \\ &= \frac{1}{n} \sum_{d | n} \left( \sum_{e | \frac{n}{d}} \mu(e) \frac{n}{de} \left[\frac{n}{de} | k\right] \right)\left( \binom{d}{\frac{m}{n/d}} (-1)^{(\frac{n}{d} - 1)\frac{m}{n/d}} \right) \\ \end{aligned} $$

然后就可以按照这个式子直接计算了。

后面那部分的组合数可以分段打表处理阶乘。

前面的 $\mu(e)$ 直接枚举 $e$ 的约数计算就行了。

复杂度瓶颈在前面那部分，然后这部分相当于把 $n$ 按照约数分成了三份。

假设 $n = p_{1}^{c_1} p_{k}^{c_k} \cdots p_{k}^{c_k}$，那么这部分的复杂度大概就是 $\prod_{i = 1}^k \left( \binom{c_1}{1} + \binom{c_1}{2} + \binom{c_1}{3} \right)$，最大应该也是在 $10^6$ 左右的级别，可以通过。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


#include <cstdio>
#include <iostream>

using namespace std;

const int _ = 5e3 + 7;
const int B = 2e5;
const int mod = 998244353;

int n, m, K;
int Bfac[_] = { 1, 638474417, 876712294, 949283602, 187142323, 373341033, 70007868, 501927483, 796024455, 542991096, 45596018, 283287674, 596316874, 417528165, 191166323, 834980587, 914550501, 688948565, 104964765, 393032085, 623627864, 982424362, 446366139, 407729297, 330880448, 428937595, 897706118, 536236563, 860856448, 945501487, 442819817, 57092875, 14554181, 511596111, 142128101, 499710224, 406984354, 372247494, 788080221, 634098066, 833655840, 62174429, 217507999, 826634010, 531854347, 83857087, 391931702, 60435539, 346814021, 201876905, 295201906, 841028503, 595254166, 288961565, 372617820, 788488293, 214785669, 586941976, 798836079, 121559584, 671639287, 905745233, 598047083, 524126609, 332670261, 849315549, 108180821, 330441070, 822163165, 644097424, 597398273, 433824922, 821516475, 558211762, 643537971, 813259672, 980160849, 572408921, 491147937, 662387095, 732727656, 426783046, 336239771, 915978376, 384818512, 244038325, 482374615, 763456553, 670866031, 970700529, 122642896, 307259936, 552245646, 334904481, 700983666, 310517972, 122041708, 158837842, 526576992, 154265204, 160030060, 545120840, 594484528, 125533240, 932427947, 483239722, 888547621, 159892150, 204604906, 953194755, 683879839, 710198568, 40172755, 230420112, 590157392, 712910418, 853172441, 199660950, 89366316, 958564551, 384710263, 193777777, 252902665, 629222215, 513947030, 433880730, 305993854, 844300169, 150494228, 12034969, 844360005, 736620499, 880392466, 621197845, 316234919, 513089677, 600187555, 162637844, 695714167, 580355949, 101492974, 190978288, 622545330, 630593004, 159596479, 959253371, 446760507, 188808028, 19289865, 438270265, 957629942, 411489774, 833415116, 639147854, 1858960, 678615452, 368475610, 97606564, 682682315, 412424033, 34035221, 37308241, 510346646, 745591849, 319020540, 56734233, 74617988, 329751033, 819215905, 147266093, 524027922, 36811456, 183951017, 90677883, 584237732, 31729117, 528753617, 356071602, 259079578, 313473995, 102311167, 365600946, 493073744, 775455687, 826897016, 330331487, 882716777, 345961537, 393771832, 816774574, 8332991, 908086460, 824079438, 223282259, 736669190, 832392662, 649905009, 546421210, 220312447, 872186518, 545208507, 526440874, 564560841, 901016661, 820215494, 594075875, 630254812, 497843223, 451653192, 281875122, 318497156, 281077520, 391564011, 985402237, 281589650, 859275605, 350331071, 110566178, 929486824, 82719024, 300738984, 340522732, 805325367, 223689578, 40359077, 767818091, 906934019, 216541952, 658294019, 303213536, 864118508, 997822898, 348600216, 835484573, 573706739, 878131539, 195969604, 73732226, 756919022, 619535652, 316588744, 178145620, 401222720, 940074300, 885534177, 812496962, 722316264, 348438629, 575985717, 599834990, 213689172, 103783113, 815021282, 860400524, 861687482, 584871249, 676542561, 346129673, 766275603, 579782990, 980836133, 461343290, 169564539, 517235481, 911472795, 54096741, 861375995, 679025032, 733542862, 505796205, 417876813, 695843405, 641311602, 951286622, 604948489, 363266670, 366263604, 168044071, 483981875, 961681722, 335481797, 610724444, 310772360, 380699882, 338568924, 730839588, 429184708, 245641763, 544232708, 20274450, 393495668, 841337447, 563955060, 577941262, 286164023, 435793297, 602069285, 552383730, 550046860, 387930530, 760025067, 885951502, 401178749, 851255079, 19132477, 811438469, 584572864, 72440788, 918098612, 204404247, 720976283, 255229675, 333853788, 977151551, 119288377, 650770098, 947701400, 464060630, 315552202, 744889435, 586537547, 456191643, 333104526, 4390399, 292624291, 117371703, 988378684, 984089998, 234426668, 331300777, 566486504, 911513273, 800612279, 582125752, 283010644, 749562308, 858022481, 684870615, 909030347, 68685886, 708205284, 701025199, 995703398, 863814074, 828484950, 932912293, 464037975, 462924258, 411054570, 449870191, 939830261, 425865548, 390266531, 838670730, 531580415, 983699513, 566538086, 708853823, 566766129, 831192378, 206579820, 37308012, 179888829, 174920451, 29923813, 301188781, 741829521, 657979351, 821511104, 590730766, 593164676, 231588061, 800834612, 245884933, 936704636, 770845925, 303004806, 388137181, 135272165, 173112946, 247687458, 676146427, 589312043, 205628042, 272876741, 41047791, 963120036, 232528387, 705428274, 775817031, 266419267, 669489805, 276979681, 471733299, 107060302, 937835947, 631026019, 605154426, 877328108, 7362571, 506268060, 522147012, 347010609, 897850418, 570335076, 6177705, 771152172, 713858514, 178011904, 689869762, 936268003, 193864340, 666780762, 699888911, 676150645, 166873118, 922700952, 666879233, 380386949, 760826274, 443834893, 725706872, 443657887, 735740462, 905906528, 328979964, 72564175, 197593783, 486514627, 226471935, 470135404, 497601756, 382643551, 366208505, 800048116, 954410105, 171703479, 749544729, 934051883, 186302178, 117565665, 28515366, 556127188, 165302301, 517407446, 832761782, 129452649, 393456657, 173655801, 925142654, 39806322, 297193538, 419427422, 320214110, 74672160, 478922755, 198854937, 951720077, 298024541, 871933197, 394880724, 822553534, 390632053, 278310054, 693543402, 821825588, 252104595, 774273828, 870541371, 413412181, 468705875, 153029405, 173049798, 447426627, 112732874, 512554988, 689071146, 385605303, 209873720, 282897103, 232240472, 693187928, 346011894, 928693088, 882275125, 876497899, 958225129, 305917724, 451486982, 630091198, 356048018, 325679625, 67310823, 518026008, 459335532, 895187265, 705767517, 603655893, 128774695, 648690264, 808258749, 134184555, 506333429, 501958182, 375160961, 575505950, 393573130, 88195602, 827220611, 748694047, 68190615, 214323896, 281445790, 156691339, 916923649, 939065335, 276074031, 822569548, 11597655, 326103418, 552199946, 298152608, 439461455, 314945688, 738026177, 694814243, 671139951, 623015619, 752565984, 717432981, 385460530, 711326704, 555396846, 317971426, 726156597, 529769387, 554596291, 898735222, 603182133, 15019057, 640377761, 216846033, 233536009, 338335716, 695413992, 916128300, 582989351, 486482314, 392473715, 157046045, 440133909, 979645207, 171001823, 980701383, 329609648, 362216114, 665296408, 305452149, 443404632, 435848803, 826373774, 467041349, 451783592, 361204798, 470555993, 502324157, 903147162, 308057484, 119542277, 347833149, 457648395, 434959642, 708454989, 106943594, 372490496, 385510728, 388387295, 211933849, 458819803, 592329486, 904737188, 32004291, 829555360, 71505438, 93458558, 78988746, 132150611, 76680600, 241322250, 889907850, 454565719, 577443503, 91306733, 33396591, 54296524, 623828097, 729012741, 489271002, 569749913, 718586252, 686156489, 214043693, 561649640, 521131116, 322168493, 713476044, 745829775, 528827131, 445043596, 115925492, 63602402, 267362755, 302400315, 923078390, 40685739, 570334625, 425218947, 300566622, 154721591, 975635122, 681055904, 560006512, 39952100, 991716635, 548996041, 222059821, 925368876, 912995247, 83494668, 474854801, 477211096, 257118263, 498240557, 945994695, 297063515, 343363294, 922935675, 212820659, 810862062, 276719840, 833792655, 758360114, 772735541, 877820275, 984614775, 461853093, 148073889, 770537802, 186103548, 229542528, 741797144, 308010402, 482353858, 819735799, 687077719, 74731896, 30003378, 63710828, 532365990, 883977343, 930484262, 656311650, 122275891, 879154192, 915887245, 268372735, 173770156, 269873549, 377742973, 51275675, 941222802, 545484874, 748280238, 46486013, 58593926, 677432735, 738257061, 21881554, 605854640, 887710995, 474842829, 674783621, 267726409, 553978642, 891554540, 700451655, 7073772, 95183385, 848867625, 920632493, 400176109, 409080008, 234032702, 100988948, 333528883, 697644778, 97522948, 325275913, 515496652, 235673487, 390377694, 262800898, 45987398, 897079383, 57638961, 790010794, 30413416, 115403281, 517050512, 692919799, 360642718, 461749160, 76590405, 13198445, 567827302, 505712943, 935404028, 567109428, 424654706, 577595408, 946647976, 882088760, 383892745, 658474566, 145066889, 339045014, 288595133, 220173083, 809196985, 488724138, 715797300, 812500088, 390872748, 198395437, 209809677, 251680896, 139804320, 677703055, 663506382, 695347814, 70091750, 292264493, 306871020, 494320490, 766389361, 40517433, 367534638, 25494329, 923139353, 249490179, 12629586, 299070408, 870843400, 211756561, 659238894, 850635539, 504698718, 569606286, 554227444, 952543806, 110877109, 65118888, 558805924, 853457929, 445252148, 571935891, 22129538, 979023484, 188912279, 256281795, 695965747, 893757562, 763080960, 305074154, 65231491, 634938288, 912911566, 311587357, 375993408, 546541568, 69072133, 939152092, 292698823, 790020967, 405540822, 155093216, 553969206, 817359797, 936036643, 192543744, 749696762, 915495697, 381995158, 316762863, 94140449, 963086402, 413126101, 979485745, 37563575, 158394770, 544711799, 311655841, 933641832, 243010205, 963056710, 724471925, 602491279, 371919617, 802417742, 619165135, 334646013, 624328585, 232957550, 214996303, 162030595, 574791029, 886754778, 38088885, 326425271, 333007835, 722417626, 211906626, 484123887, 743006309, 283059531, 377929821, 590008446, 14252420, 558071312, 848568426, 743946412, 409141798, 248332941, 796671445, 832357368, 988034679, 631542916, 162026842, 678384283, 172276641, 405207112, 409675070, 182634135, 829303789, 951352281, 18063742, 368518581, 988977552, 737310856, 960325981, 104121967, 374544588, 1884078, 355808744, 385892669, 638607426, 273169986, 596868491, 312790136, 784653222, 607304611, 525479491, 715745570, 10606982, 133670326, 751377777, 813926726, 521733954, 277617484, 336265578, 35834555, 564087599, 219065921, 343961025, 515203686, 313632531, 150286151, 694163251, 67384247, 269647422, 18058363, 230943242, 547708338, 52161288, 538224444, 656121134, 798823564, 886184101, 944959217, 535498408, 40763559, 912779295, 244779964, 876020115, 523124058, 562910912, 889316514, 971894705, 275052166, 623016958, 495867250, 565227944, 376005807, 204446673, 141178261, 48767038, 457684273, 933554548, 127826711, 742944255, 210864657, 487318395, 951127803, 209305987, 319788637, 659137294, 976295813, 561525552, 183064490, 527803521, 715390025, 54138287, 873594068, 817557371, 821228911, 865854329, 18862495, 430238957, 667630300, 462554005, 324322857, 189862383, 863799064, 638544070, 700943861, 388911184, 109394926, 35807478, 250187515, 850048805, 286059202, 595613028, 498643547, 357103141, 351853877, 636456178, 312649497, 655494525, 245942980, 839700535, 421290700, 676412450, 909702106, 793598459, 285843479, 832276048, 238607386, 208830815, 147954033, 540440789, 726437551, 184348260, 848435923, 480584356, 252862701, 526417714, 397798371, 691522880, 400731148, 101133665, 252522639, 878164518, 985130003, 381270337, 330583810, 386147469, 587766057, 789544102, 625975158, 474173552, 674313019, 418033105, 594767143, 62163978, 790870663, 274769381, 308013743, 509456888, 237717712, 157045810, 226519400, 508818359, 175635693, 281117739, 966318684, 272047186, 281918691, 899835088, 559379377, 412419409, 117153405, 32567116, 955814250, 699002119, 177896584, 712896591, 767682626, 641598662, 503281057, 758380660, 486826649, 808701139, 511479298, 498997878, 806172108, 119444874, 144672106, 221879805, 993644796, 699534338, 338909703, 867251263, 722145963, 549347798, 186743862, 18536028, 319624670, 253251894, 718791946, 632859338, 41814114, 536832412, 448354377, 777914764, 692260461, 245606459, 773628426, 107128109, 973925075, 5034412, 140617938, 455404299, 794274468, 380138257, 327840352, 250512392, 994876440, 598001182, 311999258, 394484143, 57084755, 598687849, 852238642, 581475169, 239270658, 157807456, 72355546, 536114498, 209498896, 277096143, 261113192, 55917823, 68847230, 398487191, 545023245, 40258068, 855448818, 986549624, 83919888, 504174407, 194807105, 528902040, 258157503, 710487178, 679847579, 325341339, 467945713, 772086096, 669569604, 606089443, 884328111, 533760024, 579210533, 656709079, 353885019, 896332013, 829392518, 522716276, 308491660, 680599894, 880836012, 44551570, 364866697, 465201045, 378473773, 737358206, 52859469, 53140903, 405642641, 459387570, 202713771, 365800865, 192383808, 848556095, 301134762, 785454372, 530316421, 950807601, 413840829, 760334679, 399586250, 41923036, 656290745, 726780130, 699590035, 485457499, 690001441, 111874163, 308669338, 566931363, 640827004, 325669309, 975460780, 684479442, 967269373, 546969497, 388689701, 932126951, 721695220, 399980339, 749602473, 472949993, 518017122, 147559016, 549687820, 159788463, 247686020, 470114481, 256847336, 932446869, 159111724, 872185857, 545826250, 662205150, 461871193, 218592929, 13037169, 143212400, 696437508, 191849336, 675932866, 151889553, 896456400, 878703498, 114186730, 314795475, 633895291, 418918400, 255290913, 595884163, 811539323, 639511321, 89805971, 192443742, 825671035, 246883213, 485041591, 168382150, 714976582, 295898061, 696818315, 611070862, 163789266, 140289851, 725068512, 759880589, 701148374, 242300526, 533042609, 506130339, 4302336, 1294247, 410992377, 185688203, 752958782, 353070689, 459320446, 878306150, 697876761, 206837612, 477909706, 754669485, 611607455, 380493034, 662830731, 559289160, 155312119, 114532351, 915834079, 945274406, 79781699, 298263705, 778838607, 335552400, 529216101, 878094972, 952119381, 219827639, 861214371, 152422062, 840903973, 647310099, 552748497, 119063763, 158552943, 367416824, 888392797, 916525439, 748635378, 550383403, 973366814, 75923430, 83240752, 976001238, 828804575, 848259019, 745478018, 114887925, 937624887, 265623514, 462421750, 366707320, 367924553, 846993133, 923119693, 667227759, 174378703, 418329548, 738133676, 562397423, 897917455, 319069390, 40062090, 423511585, 296804580, 81800722, 114346841, 342324676, 566524382, 152058535, 956276337, 520288073, 830957214, 289941149, 221190161, 942686845, 925752178, 654416425, 832452686, 692205432, 420541799, 740157471, 820977660, 267169410, 831220038, 417005912, 875493938, 823166072, 728454812, 869087493, 272641764, 986020321, 249103550, 447660975, 803704970, 941778993, 843439912, 640250852, 126594230, 81752448, 217214373, 8090, 815508153, 467782330, 888470703, 192220616, 987267463, 124315590, 174714168, 973786025, 267901132, 889525490, 660774027, 125472848, 951453479, 50530621, 220169704, 437660856, 19840397, 183261403, 652678397, 91600158, 591116721, 308306707, 942859297, 354880856, 540319710, 774130469, 313241084, 31357126, 164289049, 319954828, 850416074, 139084582, 737388697, 781023184, 924217172, 108168938, 917861735, 148278528, 105376215, 675211107, 883051929, 31018348, 760049296, 315094878, 154159023, 305067968, 438727956, 509624570, 607856504, 385731226, 966925552, 51871608, 740994024, 733905911, 672734939, 614085592, 377057915, 215945066, 457743498, 499872790, 124061032, 201506295, 817586763, 992735713, 623503799, 704564037, 138937737, 454349886, 35212756, 559584236, 518745177, 504223570, 218617689, 231822660, 457207833, 125417985, 487832784, 404169214, 276036750, 84159058, 784503697, 206309646, 396363623, 734558079, 731642996, 994932386, 354883510, 436335309, 424180850, 289803077, 364805944, 902810120, 172325720, 433186147, 288465914, 715164617, 657816003, 481162304, 308380947, 148254302, 434327440, 613474447, 884361465, 18333316, 254468146, 558956496, 816835037, 211183995, 12935086, 796392703, 721146367, 884294368, 142185445, 351491725, 640398562, 953769884, 977697357, 346680870, 655645460, 246888672, 834595531, 915915979, 972255064, 535812389, 748283012, 420850780, 91321067, 41972562, 521902115, 230370581, 207305412, 394878806, 853009537, 67016984, 371104474, 633565220, 785313954, 611448374, 48682076, 283884744, 27542966, 766466789, 191863723, 64748124, 151779940, 226249422, 106855733, 268575910, 489360447, 277752808, 212604510, 498320579, 735304770, 361275315, 896425714, 663194414, 788340653, 445854390, 786336279, 805765546, 257110521, 611105022, 758611451, 805161272, 729706424, 36746501, 330158910, 596485813, 468129309, 200847921, 552903430, 961152460, 556713989, 645091350, 981930399, 710497961, 62345483, 217099119, 887284732, 315177010, 503516862, 357334986, 718835852, 913004502, 599658875, 118059173, 487589844, 292156157, 358814684, 907292236, 247311789, 116097054, 863453020, 281295633, 812972737, 643868500, 121480868, 951402810, 328970139, 85367035, 633629166, 362924216, 396332115, 395955130, 818500778, 125030221, 181113364, 499002150, 164840186, 541557314, 853292312, 565567804, 704926294, 820902807, 423202591, 82342424, 339640455, 811981711, 761699708, 734504379, 62253260, 457345181, 373779604, 246274415, 147864041, 680611489, 113395585, 707383766, 592331769, 925077350, 694680152, 770548178, 990398656, 913846362, 245336149, 888597030, 996402653, 699500103, 866682684, 238167074, 543944516, 595457177, 125581313, 600130702, 296697449, 264897779, 112728599, 572041452, 903837674, 799112668, 384136177, 337833945, 752221617, 529462989, 376051822, 480450700, 494248455, 98214173, 90612675, 603913380, 173972579, 332899082, 350613655, 526540127, 408884204, 802830021, 961731838, 590160610, 533047427, 759026369, 346122597, 195415572, 236344704, 110008879, 481666406, 873393028, 131856714, 594822806, 674279751, 145107528, 59522583, 136504873, 669915134, 801920753, 159154238, 44820432, 541962510, 220094258, 645226926, 727292827, 747002087, 777072334, 389938970, 676886948, 713230928, 391187840, 231205897, 972738828, 752481486, 415537153, 65753788, 690717789, 564830671, 474034007, 564793640, 236626833, 600061073, 380606083, 457790341, 205871960, 323738297, 23963426, 621374593, 166813684, 770230548, 723238432, 118624235, 243941307, 287671032, 973559504, 80453079, 816071184, 662038180, 188118664, 398253464, 78969719, 358919724, 561161036, 244731384, 861375753, 676552828, 199341171, 111010963, 404032157, 15007469, 410891874, 293421269, 339843420, 269766986, 752732002, 336959605, 14244457, 377684984, 423996017, 841787262, 331579622, 268243673, 491000522, 182948540, 412033053, 832405770, 462579521, 693558577, 356801634, 546702921, 25142337, 152513397, 691739925, 737863144, 934346305, 596451995, 694568954, 527495727, 652014069, 462143646, 876006820, 491763782, 650203872, 206068022, 878034127, 193660195, 463004387, 19556326, 504569410, 551134448, 416795012, 459988396, 10441940, 919894484, 122583813, 394649223, 922878353, 419994315, 593398649, 604125596, 278442527, 519738858, 929932476, 963768176, 456894764, 721553288, 481843872, 202651936, 882517476, 846760390, 498683337, 976095170, 15479729, 702523597, 772761299, 325485607, 336863451, 309635269, 949028249, 538720983, 884794485, 745987221, 624335538, 128957299, 489646786, 789322533, 659333765, 509104842, 171997372, 922549537, 394512677, 77936000, 386115493, 50865043, 387304485, 923800607, 329505251, 845328908, 20937461, 385258895, 49018815, 277896830, 541222054, 690959202, 872646140, 714787224, 911100363, 614764590, 581356488, 625646122, 574488313, 500694157, 819184601, 369182214, 90081456, 538177858, 587194686, 937991501, 993580422, 375354540, 416654030, 558823478, 401984674, 193500140, 14261622, 639095619, 3524514, 646925471, 540665426, 216988792, 847764166, 413162692, 304116919, 365786018, 963018314, 734767599, 407132657, 229130073, 743731625, 952322941, 211523872, 16441988, 661637039, 144980423, 477198733, 840849387, 421040574, 150783281, 979536721, 805651582, 172155857, 547294476, 696300165, 773259009, 577403674, 649228679, 726526329, 802820829, 617053935, 677653860, 453067135, 131583878, 305544461, 247670131, 176106281, 632449155, 929095498, 593362809, 843705280, 644504208, 239282036, 758940975, 242888980, 30419459, 162331951, 869616430, 959052755, 791826050, 985463402, 962827274, 795721179, 930624835, 122667284, 261585206, 516321755, 852592530, 390947948, 69222814, 237885042, 737313828, 835951835, 389749648, 587283246, 111276893, 452997345, 78828708, 382938777, 638584664, 488166208, 455856024, 651142160, 818863012, 590612592, 137660292, 914306639, 832413555, 939806618, 491319468, 720784236, 420320241, 899336396, 469676688, 386626643, 244467770, 668695145, 496733288, 96791353, 949582565, 26368504, 330290904, 731332496, 295027067, 182188737, 792857103, 442171559, 946989153, 830308872, 744842355, 666885724, 521344100, 105160700, 753055262, 209908395, 670313309, 6285377, 668715275, 293075071, 220131604, 905683034, 87247059, 10563023, 924835496, 299223721, 259415897, 361668463, 971100089, 226968298, 760740402, 512017253, 440777209, 99649743, 519917946, 739992246, 826265493, 58953454, 476222250, 824386193, 97151070, 111960112, 219436620, 687289480, 391726954, 604890028, 633652060, 591607843, 247747483, 678073819, 815450593, 918048438, 242366855, 48354316, 219270256, 498897396, 516432938, 85284531, 56995494, 979294232, 914659468, 386972415, 854842065, 754079663, 642786658, 458603790, 996212724, 838103435, 876705126, 365887989, 817047628, 610073831, 949716511, 289235445, 803644094, 882832171, 444094191, 308045603, 613338053, 698025609, 835786784, 72480267, 711468923, 726172731, 189972995, 322888445, 665038087, 288851183, 675202693, 622429752, 845794575, 11584804, 394994592, 712810838, 206029625, 743809429, 301029012, 757033316, 812819242, 974559244, 674180764, 723617861, 367711797, 733215777, 742398359, 294876390, 113763819, 22035421, 959486572, 858559810, 523005355, 778259899, 609124230, 882672374, 898089066, 800576135, 937766095, 325993923, 671629636, 343145762, 941601677, 535448641, 128638019, 351097457, 947031904, 440740274, 593907889, 858256620, 651200723, 94266795, 417593196, 783573565, 299272677, 715624485, 635292517, 83086894, 673298635, 984206523, 542843971, 504474428, 359478109, 599533244, 134519312, 904684853, 659955603, 881173342, 655712590, 450046291, 735928439, 194548795, 972774406, 173350007, 287321583, 739105020, 376902792, 784491092, 868198597, 394283085, 648465952, 443703262, 690154031, 169013813, 16422871, 458780403, 337974759, 146999583, 585161712, 367061625, 594319722, 854563647, 568434953, 697502214, 618177955, 738141043, 542099463, 248007459, 573994984, 535084676, 299174432, 66628616, 578943699, 285943986, 746900711, 903903635, 742314795, 607883363, 675831407, 229731324, 535915879, 311480923, 738290568, 3134056, 94704928, 106243257, 703692941, 856066867, 965907646, 49633724, 972242413, 883520028, 221925665, 401920943, 976270161, 820696588, 409911108, 274832651, 665949756, 352639283, 631573115, 316896483, 254970102, 236277883, 455338890, 137768685, 955911337, 160454905, 612745912, 609520572, 419254833, 628030298, 162620329, 813282113, 577741576, 234193154, 948010625, 909727799, 892454686, 157317951, 174446986, 853284937, 187596630, 901222267, 700818032, 516363789, 911998295, 975021362, 624900982, 117598902, 556611288, 637288257, 552836752, 927122298, 886216966, 439575442, 871469759, 980162121, 686321335, 352486390, 365457908, 385975035, 845606909, 84924870, 965740114, 459102643, 558220791, 412374155, 927606072, 908613773, 650237056, 93379555, 878832641, 506664166, 768668589, 34507081, 614249794, 220035602, 353631992, 258388385, 192152781, 739238802, 422199459, 165913238, 908362104, 350255133, 255263058, 322575358, 566073550, 813032469, 116007867, 134035304, 595475717, 816674343, 771449239, 728556772, 871861964, 967916935, 864877926, 174031496, 926829282, 563096119, 326549798, 171259407, 218872798, 43745938, 886925642, 863565863, 908752311, 64716978, 703211036, 12775780, 931947039, 874007723, 702731056, 244643479, 853945023, 585315061, 803597299, 789916432, 286374238, 745768395, 629141541, 613676466, 953559789, 625414510, 423855595, 366145469, 880336545, 87335825, 797531927, 333734234, 599650552, 282280109, 724671071, 451165139, 256297014, 370248303, 128761001, 117377529, 255028448, 895870714, 440724648, 58852065, 308653660, 281552118, 455980650, 953662571, 474075900, 795392505, 281348468, 71916322, 255585641, 434816091, 664197732, 185792743, 222918487, 828285082, 364856903, 169212958, 548447756, 911828063, 644503498, 149123648, 718045173, 630806417, 972393845, 862839484, 388854780, 736227254, 832986400, 916456297, 573433356, 314693916, 511764402, 663678493, 515575336, 428068270, 423183826, 567900378, 153529304, 378440984, 70891382, 419733481, 642060086, 706239578, 753773333, 437238788, 888483202, 869729486, 669908167, 664990744, 670313061, 238933227, 564423714, 767739357, 173199128, 922377714, 336564048, 579196148, 344355077, 632912142, 452390855, 757103493, 211287250, 693195921, 435745985, 960268965, 100189123, 564150498, 284209379, 679960920, 773087916, 855479832, 481827552, 433802090, 713277676, 393934171, 51370348, 177090598, 961178945, 694093380, 701651719, 403061033, 612179701, 893262054, 420881731, 524045373, 496971759, 464400965, 709844862, 146178979, 101615911, 831753030, 200986212, 900026737, 220987644, 864484781, 251718753, 269235518, 498311664, 734686163, 387016592, 272779384, 844520957, 130659604, 7080469, 661917973, 683379259, 968404926, 805217854, 203956360, 259240348, 488844621, 155358248, 7529639, 447193381, 381466282, 881783783, 194512089, 252082398, 679935071, 359944674, 659478190, 544001661, 441485312, 502082022, 323738429, 445719559, 755335634, 360449440, 329588615, 750732621, 740782647, 347511077, 206794321, 901599231, 372193140, 546525906, 98613054, 109218884, 303110828, 298050489, 985524427, 443773412, 128459410, 590893716, 86282010, 548033568, 330887234, 812956643, 687294533, 948511601, 333772553, 464112846, 772333655, 721084229, 31835478, 331916427, 533592369, 357347436, 651001706, 871975748, 752533273, 481515942, 816679791, 452722766, 416273693, 730387628, 783543268, 777115208, 642920384, 503085651, 93829695, 235070863, 620014456, 223341051, 538597437, 655989476, 278056139, 815903428, 707971922, 746721927, 930661318, 749801573, 449409696, 699287127, 914153187, 334885743, 833938200, 429759848, 626291316, 876302615, 466041862, 425565564, 278985149, 503803540, 547723012, 428105027, 868403596, 217613784, 411643260, 474844534, 888238707, 392534750, 803473052, 922186089, 22753517, 232218076, 346631241, 760590919, 510661570, 893678582, 769865249, 917928671, 810358415, 539001034, 983538502, 730641039, 967064402, 474310493, 701394315, 995370356, 616996159, 798322301, 76591944, 891854924, 239300981, 231721356, 302285242, 474417140, 102429294, 218582540, 326973501, 921448953, 918617007, 772169831, 501125854, 426068899, 247200193, 626622487, 228649440, 660946303, 722403656, 715477049, 671794162, 198467931, 643696492, 742756734, 963103784, 605152029, 651545852, 462660570, 663270261, 220884334, 396881088, 612760233, 376483161, 364187931, 708582028, 74340200, 753818952, 848867837, 350431704, 72059034, 345111886, 932474797, 791216072, 671823672, 812319607, 462569962, 334451149, 718995099, 633125919, 30988619, 504541050, 531213622, 350378112, 226166717, 523443516, 595389696, 180591752, 683141957, 386814657, 518422245, 255692174, 673365636, 317446209, 237594135, 287092115, 548832542, 827056161, 650760543, 451479365, 892157578, 177978881, 200411187, 651780991, 546182474, 203041679, 269285553, 866093357, 688684808, 119366536, 667327485, 458663531, 80257141, 313316312, 465211069, 35032685, 541239751, 917768447, 256667636, 605313606, 168706957, 182900375, 750117193, 33032014, 728508871, 464039832, 933488501, 696936931, 503930295, 249619035, 269173385, 196063152, 855789313, 218680834, 663053607, 810979765, 637623901, 47569040, 889679555, 900453742, 630540173, 219548125, 811351181, 447157254, 48293872, 252767931, 958902297, 681449865, 296218814, 229958401, 853870159, 452358286, 125943352, 439152913, 62402409, 682301831, 62801862, 177076138, 748259163, 69570431, 151191712, 104676054, 986063012, 224735177, 71921532, 892227618, 124164816, 829872466, 213177421, 960467929, 269013494, 871688962, 978059858, 42926916, 537087913, 635832597, 651741378, 587610508, 969123613, 514588945, 92440114, 20660049, 666765961, 434279634, 513856225, 3907296, 40501448, 197524035, 281871512, 415497414, 175477963, 189098770, 544177744, 12585949, 286592050, 109328730, 643691767, 126621521, 193241990, 645469437, 379407277, 367253353, 584459532, 297457955, 102052166, 205393297, 23840954, 896624036, 217127017, 163298189, 8264903, 44123638, 116360014, 880054954, 873938719, 194598855, 758373441, 502483692, 459233410, 617583886, 196981656, 454590544, 166464286, 492245792, 986843080, 812441428, 80557198, 369548829, 936650186, 962390239, 433418091, 105552005, 20590957, 242273101, 580971332, 840528210, 886788488, 501678118, 497580226, 665147020, 803575161, 762288537, 355493809, 419413452, 88900164, 990167611, 673447603, 179294895, 901634007, 89866970, 492495082, 128625385, 509849185, 575987650, 826426395, 577256185, 348974809, 532070310, 444568444, 616059995, 414194257, 818744640, 394411763, 16232745, 443012312, 43908505, 977026668, 804019338, 461389164, 659160562, 360211014, 750462725, 732686070, 968896201, 229855967, 240982196, 815178512, 324741802, 197991923, 687413213, 541144612, 240107673, 648599644, 640036075, 59809521, 952962089, 856505535, 935796702, 992905138, 398599610, 677556704, 870177895, 345181024, 593682394, 325666688, 224925603, 901456741, 934223928, 900203387, 154765991, 785527811, 581404502, 184139999, 511100545, 159186619, 972405939, 426214511, 226316709, 399705618, 210830877, 945243221, 199203725, 811858592, 714155454, 386454418, 631101690, 34547625, 681858171, 160235707, 84493735, 645422849, 526859451, 248807068, 709757129, 974220646, 268994020, 250959694, 148576677, 19371682, 820097297, 233191193, 846957266, 580279368, 318300447, 2191828, 848633697, 935092683, 506687987, 901220987, 481459931, 539567484, 743569393, 282424433, 26691239, 729073424, 860597736, 475044977, 177903321, 24188730, 551556379, 436357857, 735589161, 792972519, 614286794, 926316039, 743034339, 567854358, 648437466, 516167226, 151357011, 143068447, 64707765, 193691951, 311273254, 808637654, 272522795, 190701933, 336563763, 829880625, 218058015, 909075057, 540927150, 466246599, 368855028, 786112034, 925898147, 522559601, 394220873, 188514425, 850407126, 450378479, 769707451, 899612407, 215311924, 84202800, 392017718, 286251537, 479544467, 668806484, 94214098, 163976105, 565857838, 911406244, 551435120, 30019651, 794424877, 33218812, 323151525, 906613099, 121701603, 681384398, 614217983, 782493409, 807101118, 176055335, 567454212, 853746420, 8181284, 444528833, 865461951, 286653714, 355689698, 54954215, 866192723, 553631971, 838853823, 921280696, 387622807, 426963589, 286620803, 63876447, 949322705, 361760886, 351755097, 984061713, 820629354, 983685054, 889135077, 965214778, 888573766, 419062603, 732044144, 913768172, 995350063, 302767023, 526402934, 70552638, 447453679, 171297128, 977070668, 368190929, 981731104, 225210951, 636262729, 110954576, 647142829, 191882124, 772081349, 562980566, 83922475, 60634971, 579150121, 312895656, 212904780, 51568171, 150274796, 844462574, 548478088, 562983131, 60949367, 465284724, 364394020, 204715419, 727814670, 19533020, 322226329, 183566168, 724333004, 328063440, 510592752, 276171166, 327928634, 52458807, 582501116, 615419476, 977524177, 566574988, 883205623, 344382954, 341370469, 54122358, 959181460, 480158153, 361934895, 912573425, 401918906, 802684215, 207544377, 755652024, 286207526, 40174926, 866739461, 210824168, 668830073, 206707897, 661720836, 568479007, 425142330, 590246341, 384156962, 566396021, 369414407, 593320145, 280606414, 414163604, 706877618, 878128430, 411742951, 761341407, 193301813, 465989488, 548370000, 8294322, 949836834, 749570167, 379912287, 57885333, 442312776, 187044007, 366933789, 688081744, 322956817, 419699361, 851406178, 11470970, 16574381, 396315381, 949643886, 228086005, 600191572, 750385636, 41785937, 849101706, 219222295, 391667731, 436444811, 105083968, 158009352, 656087823, 328736286, 473646076, 53766182, 257034880, 584902453, 30645366, 827091129, 89255697, 808411380, 507001848, 215162519, 692374171, 121469295, 507231913, 113371283, 604947226, 434264625, 348763373, 825243013, 476935929, 236199953, 180707885, 776822307, 953526515, 643293926, 718439098, 762617700, 21874873, 689689577, 444935230, 411423177, 674797408, 362026478, 894030634, 675610856, 803407599, 159242971, 867608454, 829317990, 22554175, 632441623, 617679741, 103113383, 952628462, 185446735, 766760224, 258447428, 18653828, 908749844, 460774480, 263006576, 927429592, 173685132, 199348204, 462348776, 757681534, 210505189, 491698560, 23370155, 73507840, 61082578, 546791557, 131196700, 312895519, 629521119, 681666415, 767463094, 352900288, 142064581, 329771568, 947466395, 188075141, 975254295, 309980833, 618313851, 12206799, 37792560, 941195987, 575749846, 133527905, 659767098, 726730059, 978464016, 51949427, 75778666, 933746852, 218322651, 140975223, 182431188, 446201733, 978860867, 863081148, 784719440, 897376809, 195234529, 59215985, 494052526, 921785397, 207637164, 288903997, 161179205, 87496483, 410436352, 320837890, 574761275, 439197472, 312114682, 963193528, 254232494, 377078580, 259779111, 123471668, 720364313, 898211399, 250523733, 511621808, 104401589, 676568476, 805430653, 463263515, 145770512, 949841094, 921085980, 865596423, 708180274, 882749888, 34421466, 548465725, 28277201, 850756943, 943124465, 353052244, 764676482, 164147939, 44273894, 872053396, 673013740, 857553424, 853104621, 538664274, 631078482, 603216371, 726262252, 655407188, 32843680, 166861622, 645817459, 2573502, 287526682, 746744346, 743415395, 831928009, 446508498, 650675936, 687752220, 772287179, 519795821, 715948127, 674418745, 547498225, 602427948, 430682817, 291573802, 141075040, 544375192, 924112080, 385334046, 122457246, 707697400, 534072066, 385643091, 707719861, 896026294, 654245223, 458599137, 794973480, 143513653, 413809004, 341001400, 915004119, 883782693, 202936283, 506579349, 678515194, 927303505, 869723371, 905943705, 225376470, 322770518, 214589039, 805963889, 134842161, 282857686, 391933828, 344786236, 313106351, 926403195, 481219197, 223555385, 1629499, 262132854, 134241631, 813415337, 870863860, 487593718, 400034567, 994489646, 411670648, 941947566, 519658145, 488248149, 342071802, 255703671, 720345751, 480273999, 265769800, 959554435, 877283263, 165910246, 358859939, 791715397, 263553238, 75187258, 20591569, 254623345, 408753255, 325742733, 579224315, 920778509, 614310318, 468381897, 617209068, 131146296, 335001095, 766268949, 415812467, 954507602, 526825098, 733227729, 334226426, 172922144, 689116289, 535405004, 403406769, 179969253, 64404368, 325451103, 225526518, 418067497, 649367294, 281500398, 411753420, 890805692, 707787492, 119743149, 512318142, 554603050, 323708035, 340819315, 820453170, 288791777, 601404861, 531223980, 603644245, 79767669, 955559118, 776543549, 372220074, 253896843, 860664276, 242484726, 11998264, 559823889, 694440076, 304161303, 536413695, 269781682, 429452935, 512988139, 16965043, 205340854, 289691664, 3539578, 201516782, 116563013, 707803527, 887949257, 424238422, 232483446, 255336791, 576699812, 943193558, 542202517, 170958045, 704624663, 218525078, 642896614, 581561783, 342882080, 984289287, 875554190, 349751626, 242221317, 461546440, 166393488, 46283078, 215255086, 62719106, 656243352, 286856802, 833841915, 379629428, 384759575, 605918083, 127003478, 763148293, 68866378, 816889980, 648103769, 641544481, 807722138, 466178261, 703351910, 254364584, 926419773, 788080170, 328101383, 300255531, 12272668, 764588623, 556901372, 234501930, 570935836, 536663662, 818239318, 150896699, 302703328, 573048654, 362191589, 457760886, 253151120, 597554637, 675114778, 488712076, 682666273, 97856807, 659315718, 960720602, 483066395, 125217612, 918256774, 393453192, 653799428, 400574765, 754407717, 771557187, 181366252, 90432862, 744965282, 428394983, 582547026, 469528291, 833100011, 105941911, 347140977, 472709375, 971630730, 769640186, 250924244, 619201192, 911615063, 455505101, 664888038, 522277438, 806851596, 743371401, 684492244, 295015721, 297010667, 935209969, 641382840, 828050164, 865849321, 746857728, 605166278, 446540967, 347501384, 935640947, 909557571, 74277182, 184639537, 259740169, 437082669, 680081455, 492480060, 157247760, 717849831, 421012936, 539598789, 686012810, 775930891, 47091425, 642877651, 337904334, 294758097, 939702814, 634761317, 289407955, 697394913, 994282435, 499082462, 373510154, 614689006, 817232406, 228169720, 19536133, 482493730, 620838535, 514470733, 230157941, 548753627, 474022796, 118113109, 908934043, 632727669, 593243221, 972494096, 730606012, 262131366, 606099055, 563850263, 321448905, 913053716, 43517848, 198766865, 185475971, 462639757, 969237802, 717327818, 754075136, 687419227, 491401112, 256738618, 466415123, 378938294, 396799323, 49348482, 427810475, 548266487, 650084514, 657976136, 769842260, 157654452, 45589178, 282635009, 864535682, 116075727, 29550277, 364392467, 506466886, 433009242, 597572477, 437247124, 139292288, 407711601, 860830935, 888075117, 706683328, 960051373, 846540019, 33107339, 897387201, 535478788, 484854818, 557635493, 517661450, 294565899, 162511342, 217062483, 205744478, 467651311, 104852699, 619284159, 921277985, 356522734, 812398757, 975099999, 931348671, 850331416, 922547157, 202133852, 911644448, 185843982, 974445050, 213986666, 431839017, 971838121, 565653344, 782023267, 548304623, 709549400, 655045473, 905162165, 520984268, 902585392, 99643620, 976386449, 351584221, 447646372, 565860686, 773282878, 939655476, 765305740, 423340934, 632684135, 290471030, 5250326, 384359258, 929815121, 868617133, 61134552, 433879572, 388051796, 211234310, 346771112, 129206504, 174671334, 961617281, 594139590, 538485916, 929147251, 134088395, 332481734, 804218505, 227575277, 837008968, 715146915, 172165484, 414513123, 160338146, 422332597, 423389191, 203272275, 959400038, 629800791, 353775281, 57259927, 822018130, 194909159, 256644252, 469563025, 628803011, 253303129, 553500057, 58621692, 62265336, 847264029, 911205590, 569138008, 656402912, 835064501, 311060327, 807745356, 325963793, 41770045, 851685235, 972563943, 26001836, 997216722, 960411173, 21197005, 410848505, 696063419, 636254864, 544071078, 264793769, 928380405, 630020964, 739636779, 944529132, 326416680, 493551735, 767232757, 315266012, 232619872, 118842991, 507865868, 346707363, 672814693, 223884498, 84257200, 458917832, 138671553, 249651962, 433490648, 763248924, 683631995, 783724274, 323097426, 806826405, 687559609, 678021435, 863392583, 916736917, 865666964, 150907932, 472793431, 962204141, 326189693, 390909379, 401832452, 207892461, 539523756, 659638846, 196236775, 242726978, 914688565, 288282640, 694053656, 238224020, 766752066, 702430135, 991301384, 26327533, 48486564, 959173604, 578270158, 708446364, 128348737, 973395811, 390269102, 272450352, 242912964, 935396087, 457085846, 992293822, 266144751, 462441329, 937839395, 775234193, 744816299, 689343159, 723962524, 919211209, 22646332, 476631694, 647844047, 938060844, 955870985, 227655372, 177284763, 750185149, 734597703, 623256769, 553131371, 702429415, 575284290, 407468436, 97510275, 554701193, 374065901, 940057038, 52138662, 710567700, 51855733, 169855231, 802105912, 600825502, 422314327, 634951777, 629007616, 684764381, 651429746, 668090293, 583464731, 719169602, 116171569, 616812432, 194256847, 937385045, 564737074, 339187908, 709896143, 691491630, 933240841, 475119050, 580383542, 769560352, 863914044, 614826778, 714502830, 330903187, 287066722, 708653625, 89312601, 40993711, 453398410, 985909263, 301084497, 500502656, 820235888, 863184644, 442130280, 598410600, 883448504, 749063595, 666937879, 341630268, 662528510, 742839013, 239329111, 687465785, 568093082, 477812264, 849786046, 612759169, 275968173, 167565536, 343568116, 547413634, 18591377, 219622855, 180185753, 130492893, 551027440, 419142436, 234744613, 173657981, 690071657, 46219460, 442202439, 774014314, 57953956, 594749548, 457967843, 941600951, 118999147, 87259356, 886460769, 170661061, 158013406, 722587713, 735915370, 968020070, 141775306, 637073231, 879975605, 971483785, 681248316, 811059073, 471564060, 785513967, 482003677, 996872768, 31109516, 447222237, 181002475, 652981849, 326727045, 544563167, 701248503, 403761561, 512560867, 286769863, 246661405, 599797734, 182386413, 817931081, 548034568, 732454403, 577221870, 565858314, 869105192, 632273904, 576015405, 69656699, 840824428, 543991636, 568602651, 637587950, 51052704, 164564338, 756326079, 938409154, 173511054, 6544303, 607243022, 582059008, 932096551, 135289050, 10958310, 639019927, 457576033, 955084773, 150007855, 554955500, 661745248, 366039506, 547538118, 112487365, 943192237, 143936312, 663284735, 886890211, 944241793, 192526269, 150059187, 304711582, 421779097, 978912218, 897983911, 71717720, 367619635, 35934197, 601096360, 961628039, 707365961, 348991447, 868093321, 17532161, 240232720, 554915517, 17028594, 593450905, 243203844, 627280533, 473830455, 150029906, 816617255, 22691591, 710239542, 306093006, 484500944, 166787731, 395829959, 70255649, 266006850, 100549095, 366830033, 741557556, 261743865, 239580600, 363963677, 365610561, 34907454, 228474833, 480542196, 960130817, 154977923, 140260596, 776408079, 501529947, 992387594, 35596410, 870341658, 304180483, 735069330, 749448411, 492517985, 654256447, 63607040, 481760312, 597887170, 855437455, 905730134, 953297493, 302709049, 19997707, 796751284, 864674001, 758058902, 784924146, 670109418, 426832104, 983588375, 395529997, 256962216, 823017060, 988402373, 362087694, 156010331, 563804127, 699526705, 569026004, 92568710, 825833840, 893106215, 627152463, 607701910, 242958210, 539880795, 782699783, 900917749, 649774792, 568342979, 234683685, 235886641, 802308798, 348641178, 907910635, 52626619, 48255822, 900552967, 987893927, 104361415, 751843490, 143935578, 659229224, 692200743, 274397653, 116909119, 128019192, 956811939, 342718238, 368411962, 62806842, 517517337, 855038826, 930711874, 279150975, 574857555, 164854598, 403636264, 819869053, 505965820, 353417551, 870735150, 626316896, 555340806, 476520498, 40061330, 968603057, 602650849, 865021171, 859223681, 822203768, 645007223, 112455506, 920327142, 934433124, 681051568, 48663714, 132654087, 386398410, 51991269, 490913702, 82627507, 254146120, 355967270, 36134523, 9322961, 934786222, 404719250, 839561982, 45758872, 766631257, 881129645, 769619757, 442215012, 170653709, 124794668, 198591086, 927360884, 732614296, 543042671, 37844313, 51855, 333073045, 237673023, 391716915, 163524507, 684629909, 362492290, 842392605, 116266913, 729108319, 671156429, 98647530, 623235494, 736921347, 490867505, 743583659, 22588584, 206033114, 993777102, 47035168, 746673419, 659938697, 639817999, 978979098, 682765157, 975967666, 441342640, 649650998, 382710072, 53842115, 261162900, 560212561, 650559057, 806117495, 817965276, 757172910, 361846034, 548742063, 677001598, 757179922, 698000394, 586082536, 862833967, 591385514, 339238384, 602488502, 801059179, 917006691, 774884612, 909741023, 362108083, 297362352, 329261613, 112712901, 150530547, 559466893, 561106230, 668645110, 175260501, 158444563, 2490351, 540161396, 224709594, 107191713, 140949492, 675208713, 347237043, 660669524, 508680213, 993302799, 65480284, 74681400, 218107369, 738190542, 551621442, 573728725, 320792950, 37239095, 342218055, 137578883, 664362197, 865784575, 178265160, 526252940, 475122706, 677110174, 632343006, 854989312, 777898568, 443869843, 856310131, 403893323, 204297308, 367028173, 605400098, 555135257, 41725719, 357463998, 576780728, 689361523, 919298440, 670553151, 446079298, 410683143, 769596520, 704489618, 274782189, 269198543, 935632811, 801661499, 357745722, 608706956, 516540313, 536047622, 474900284, 144772303, 278617548, 524252054, 221839489, 586624857, 571648819, 221630511, 121548948, 299878187, 349960501, 770454472, 938724912, 541215360, 156144194, 134084537, 503400792, 881102456, 436417672, 549737824, 650564083, 29286834, 235687447, 100476545, 117313580, 877097974, 528576053, 444374536, 716853074, 514265102, 379857427, 127513126, 558473021, 373626340, 68250185, 887890124, 641663342, 601085617, 79662192, 727897980, 159436401, 713611864, 440382648, 106866216, 265495921, 133274277, 494370766, 397669108, 150597819, 441437965, 986182139, 262846984, 790903732, 684960847, 415384560, 729720334, 888898363, 138283489, 140425007, 346272300, 568925901, 506473247, 651552450, 967750442, 167299594, 459461496, 717448863, 305614829, 364454432, 272034045, 499309445, 632617040, 265918139, 627817019, 876808621, 493171177, 93489779, 120578663, 890450820, 788481986, 460958750, 750837047, 209333992, 744344879, 675956768, 380694152, 738411144, 400483531, 443372770, 272841854, 168836226, 80856091, 895638820, 9030973, 33857526, 840160881, 429075627, 898884542, 446132539, 594952891, 141116880, 887244234, 408240304, 747979126, 772878514, 225064950, 132205308, 848643865, 242709633, 210312104, 109618190, 426428476, 114138558, 671453933, 452787741, 842341383, 281150531, 661930289, 974999575, 557481044, 85305729, 459545390, 466207377, 338060455, 559633156, 759273275, 971242416, 526610238, 644745859, 220396827, 97369807, 146278719, 667016107, 977004959, 75935354, 669317759, 79434494, 234710504, 557695235, 199039337, 766247510, 297742086, 239322577, 986724034, 224854739, 829017039, 815949583, 801121834, 855863254, 576852688, 550323884, 197588605, 176881479, 312628197, 723971571, 261274540, 416291211, 691727676, 170064248, 982549733, 918239352, 869405324, 103247629, 847203458, 686285715, 29606025, 144283037, 913767172, 861570108, 911217059, 870793828, 173133127, 377895863, 100787304, 882571148, 293683814, 253151884, 276559944, 503705146, 760676118, 378510746, 227072228, 641299773, 435227659, 912657076, 367270918, 147905845, 4717993, 544520679, 507400049, 481292028, 123229359, 633569521, 217967270, 473079883, 813097823, 7917922, 869804624, 60712726, 1323886, 798448487, 429188954, 775379985, 143686780, 421616469, 230791733, 928875954, 503119497, 279595365, 768951532, 899305835, 669777197, 927685505, 439490384, 529253919, 504040630, 160697694, 777376052, 172172822, 882012844, 162510533, 975676318, 733746295, 313004905, 958599538, 479367951, 168229155, 3109593, 732766199, 296607974, 275282274, 180559952, 603605790, 257216715, 250289370, 806951470, 251465520, 532835032, 236012568, 335115381, 462774647, 749373624, 144010412, 913680176, 25991992, 56473153, 988226999, 720597117, 994632301, 789484878, 184659008, 12520664, 470274726, 328659970, 918411588, 905122161, 282082004, 603407505, 827917393, 393634553, 664034750, 200078516, 189670650, 685227047, 29125900, 109726629, 140350889, 956226452, 35081131, 499149637, 59372704, 406210712, 748338482, 815436688, 29875950, 325795100, 368790861, 499612338, 922684200, 110114569, 486860143, 210317316, 929448376, 107727990, 395851051, 843736533, 34935797, 272689992, 713102241, 654354262, 924723613, 495983082, 958586082, 408035547, 510375478, 880348000, 921793692, 931246800, 645137675, 212376682, 801252478, 294483047, 590790899, 235492719, 582972953, 616515290, 362638524, 59888024, 977410427, 270627822, 776142608, 792517877, 542517498, 500843278, 233136855, 284803450, 632013708, 245830139, 734808241, 275882738, 583439582, 330987636, 977079279, 805263257, 934715482, 274826676, 200050192, 318804570, 206267171, 52173830, 6018349, 261005717, 727851802, 448877017, 278662368, 377403437, 585365260, 503843697, 494012498, 789721035, 244041569, 177608217, 248568082, 71452646, 206791960, 527081707, 24546255, 881104891, 39510823, 942709850, 544763288, 947296371, 422973562, 647019022, 645108650, 708818585, 20884194, 739760068, 421365014, 191538961, 354033051, 830793308, 522905943, 247822034, 851482456, 904309832, 959374639, 432682187, 881249020, 125921431, 589922898, 94383709, 69636250, 962304054, 353253741, 673933870, 279216826, 540176481, 122270842, 142912291, 682858433, 474799091, 705134856, 549371805, 79290685, 945260111, 702459321, 4452732, 967321971, 386350590, 899893421, 91003219, 700999068, 9710951, 421519808, 515264973, 97159599, 227425765, 725376973, 252615615, 911685911, 55821831, 21017897, 97573992, 804582047, 9527148, 352213091, 148392333, 505666382, 851224347, 239480646, 562169673, 926298379, 599653049, 27383361, 524126897, 239363217, 833334137, 7294272, 852509887, 48259065, 400220130, 901025063, 26157762, 584522336, 578214879, 220208835, 885262212, 598860599, 855195121, 118677219, 144113925, 18357870, 521665998, 589726961, 786127243, 464216717, 699031255, 475392745, 669207238, 869205770, 524407684, 220506673, 689613149, 675392702, 923276513, 269788265, 326174225, 979952097, 647276845, 937928886, 498910857, 893833404, 199925060, 277715119, 802186160, 661843515, 634236890, 521918578, 589512887, 12198440, 727930564, 909016338, 186815700, 844625140, 638784295, 571395090, 810913393, 468095035, 212948578, 34200904, 31789240, 495176721, 260737477, 19072020, 758925811, 767802285, 51631665, 768213688, 178469309, 185027790, 812961070, 373512090, 579829591, 336972956, 80918046, 852661846, 635154227, 155121988, 939076879, 120604699, 749790553, 467731703, 217093422, 892345735, 610456697, 7073976, 99462722, 265184771, 800766132, 573601211, 593440479, 333275954, 81856271, 565443008, 208296321, 827361616, 779029568, 177771146, 190664812, 49743354, 974903132, 559021925, 827297426, 151983506, 653691911, 153563523, 208004838, 285447960, 959051187, 490750754, 401229578, 897457477, 256850511, 637864251, 674335312, 436100884, 76803592, 3853000, 140445031, 887877110, 599605496, 426307178, 588827936, 232303657, 875880304, 810743443, 871724533, 877517411, 910589926, 308360096, 469087458, 421030271, 431450710, 536627530, 414636410, 351190937, 196243872, 78467030, 979791243, 886100267, 45548202, 290562055, 819800516, 647310799, 8525751, 147027819, 621277355, 965427816, 857902646, 636257427, 822428251, 110136096, 271351399, 412208982, 558338775, 880137836, 665110057, 620379712, 35029149, 500159951, 520181428, 507846755, 676364255, 532907954, 696213291, 437764076, 958819736, 598356365, 607863542, 97268896, 81366014, 190076128, 235994905, 509225188, 364983542, 984763249, 988186568, 815263708, 671775072, 937928436, 462276586, 15617735, 575979814, 716074408, 641582714, 43223386, 484133503, 788277011, 216264505, 586211304, 118053291, 804978770, 396173607, 285503342, 345265657, 350830865, 448295531, 781466241, 717726069, 994704486, 594948276, 66092643, 337582598, 782005000, 443549763, 1857575, 170060686, 80107212, 578592712, 207259440, 253794778, 870452389, 790970771, 969044093, 302122082, 351825488, 364379250, 735140939, 172068509, 166055224, 798556379, 630159689, 5834778, 611847780, 623250998, 363278779, 316706342, 456011036, 802146866, 239642551, 779809871, 947566216, 243633104, 823414817, 476337075, 184010266, 354401895, 724291290, 215439868, 283167364, 322291721, 548555495, 518326875, 523302092, 211328914, 899535612, 73429101, 228142667, 702023379, 68064804, 18681956, 180424314, 649237321, 535709399, 950202136, 284881122, 657295852, 496081589, 71341341, 187552679, 263662830, 878395784, 386677355, 950091752, 18938709, 240670526, 764937268, 474964853, 565563914, 646784245, 305928504, 22898235, 632046454, 740557827, 598764068, 32053393, 733885460, 105673208, 673802032, 538505481, 135290915, 279789068, 261132766, 299063509, 610424991, 800849725, 667912494, 603099643, 86000108, 864445053, 269828780, 41911324, 810733871, 261890809, 390248689, 814884557, 339995562, 102502161, 702046356, 278395191, 956401237, 828666830, 378996395, 802342572, 686098470, 79280183, 576919627, 206967135, 184879749, 935957187, 478670683, 657591941, 573876820, 626210364, 868529577, 674323032, 118527211, 526346788, 133301926, 329970687, 293643564, 530177004, 191006198, 739430903, 804930040, 389937453, 421510690, 141700633, 753855318, 84992079, 822607020, 805399558, 47001928, 155674715, 474569269, 499740540, 611562716, 998035629, 243527772, 810762228, 395484213, 206168289, 531717493, 182069742, 573258936, 962288073, 647891059, 702204245, 579446652, 756464212, 765204592, 985020200, 138021221, 64331023, 155080225, 342833436, 717490096, 342481697, 710006812, 286966169, 391316764, 641927336, 163813173, 740462510, 283614605, 899622638, 80616080, 175517384, 370909756, 19283401, 687298872, 157064143, 960901741, 385907919, 24257676, 209256830, 754870233, 353984926, 636108396, 871831819, 119030022, 831447308, 418707377, 553133511, 612689791, 894289734, 348390639, 300032176, 849678837, 846988741, 538695155, 661674325, 545346747, 632299295, 617120754, 217413506, 799227111, 461818634, 95589232, 971716517, 717332626, 283301377, 908635732, 215519117, 979541482, 609569702, 334115506, 768506247, 880030358, 297910784, 936363929, 430482926, 54140494, 158892941, 991087897, 6259065, 187967995, 178449755, 94381621, 783825907, 967476181, 542594390, 775344700, 351129885, 214821357, 403186186, 37058828, 479331293, 794857307, 689498189, 996154431, 515827111, 667478516, 129122497, 405026419, 545986228, 787570970, 835349499, 631179322, 946731704, 969525034, 914970365, 34325677, 367169218, 609346370, 776933649, 886352257, 264819293, 522247532, 707669156, 188935494, 374100193, 144228432, 508395411, 457703127, 993523725, 674441346, 670552581, 49449063, 957341187, 312852149, 149613423, 943222257, 217620728, 980735523, 871670064, 348890847, 395217883, 392047058, 649367684, 452728181, 61135796, 364301153, 614947888, 791011898, 637177559, 822514219, 734641141, 106407822, 82098966, 213660206, 186657803, 662340002, 962319210, 234729712, 93288159, 789399703, 740142578, 857115611, 105002711, 934255640, 932265522, 219067891, 317534229, 130614285, 494713237, 162497346, 422802484, 793227159, 291032164, 383800090, 732355595, 859336562, 496923860, 193188049, 308576104, 304967011, 740333780, 758659608, 363211260, 345749320, 452975523, 962333047, 20506237, 58108651, 214310174, 686459451, 93745902, 67085097, 100756444, 47718874, 500250082, 486479404, 182655360, 954947696, 221025605, 278311425, 884626024, 972423996, 346032213, 849634242, 301583949, 363566630, 669552680, 863300806, 109264234, 643066127, 533787471, 118363506, 36876722, 632826195, 305283648, 71266483, 531030730, 622610957, 338004522, 463351805, 886386745, 520622939, 289232396, 578389263, 188890371, 107689716, 120744822, 667938985, 693473107, 287288499, 526449301, 558420898, 734886266, 956720795, 379625426, 204692655, 257512433, 395881057, 589328566, 380998177, 841567207, 634380967, 417188702, 825197119, 637619258, 806721716, 596976612, 183092975, 814214118, 365901116, 683165786, 752224001, 887586469, 242045474, 450694993, 414738490, 648533733, 83334648, 847357562, 248289434, 885439552, 393617876, 797819763, 748730069, 800880477, 467700392, 760302574, 100176902, 601113034, 243707311, 542351412, 466611651, 781587414, 233814369, 489612075, 294205596, 732075333, 841864935, 254466725, 810746281, 728806094, 627013238, 371674670, 465280416, 550239544, 806669488, 766317851, 18247584, 111700697, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

int Mu(int x) {
  int mu = 1;
  for (int d = 2, cnt; d * d <= x; ++d) {
    if (x % d) continue;
    cnt = 0;
    while (!(x % d)) x /= d, ++cnt;
    if (cnt > 1) return 0;
    mu = mod - mu;
  }
  if (x != 1) mu = mod - mu;
  return mu;
}

int Pw(int a, int p) {
  int res = 1;
  while (p) {
    if (p & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod;
    p >>= 1;
  }
  return res;
}

int Fac(int n) {
  int res = Bfac[n / B];
  for (int i = n - n % B + 1; i <= n; ++i) res = 1ll * res * i % mod;
  return res;
}

int C(int n, int m) {
  if (n < m or n < 0 or m < 0) return 0;
  return 1ll * Fac(n) * Pw(1ll * Fac(m) * Fac(n - m) % mod, mod - 2) % mod;
}

int Calc(int d) {
  if (m % (n / d) or d < m / (n / d)) return 0;
  int x = n / d, res = 0;
  for (int e = 1; e * e <= x; ++e) {
    if (x % e) continue;
    if (!(K % (n / d / e))) res = (res + 1ll * Mu(e) * (n / d / e) % mod) % mod;
    if (e * e != x and !(K % (n / d / (x / e)))) res = (res + 1ll * Mu(x / e) * (n / d / (x / e)) % mod) % mod;
  }
  int tmp = 1ll * res * C(d, m / (n / d)) % mod;
  if ((1ll * (n / d + 1) * (m / (n / d))) & 1) return (mod - tmp) % mod;
  else return tmp;
}

int main() {
  cin >> n >> m >> K;
  int ans = 0;
  for (int d = 1; d * d <= n; ++d) {
    if (n % d) continue;
    ans = (ans + Calc(d)) % mod;
    if (d * d != n) ans = (ans + Calc(n / d)) % mod;
  }
  cout << 1ll * ans * Pw(n, mod - 2) % mod << endl;
  return 0;
}

目录

[解题报告][NFLSOJ529][2020六校联合训练省选2]打卡任务

Statement

Solution

Code