はしくれエンジニアもどきのメモ

情報系技術・哲学・デザインなどの勉強メモ・備忘録です。

トップ > 乱数 > Twisted GFSRとMersenne Twist（メルセンヌ・ツイスタ）のメモ

Twisted GFSRとMersenne Twist（メルセンヌ・ツイスタ）のメモ

乱数 math

Twisted GFSRとMersenne Twist（メルセンヌ・ツイスタ）のメモ

前回はLFSRとGFSRのメモであった．

cartman0.hatenablog.com

今回はそれを発展させたTwisted GSRとMersenne Twisteについてのメモ．

かんたんな発展の流れとしては

Twisted GFSR

参考： あなたの使っている乱数、大丈夫？ -危ない標準乱数と、メルセンヌ・ツイスター開発秘話,2014

Twisted GFSR (松本-栗田良春 1992, 1994)： GFSRの際に，桁間に情報の攪拌(Twist) を追加したもの．

Twisterと呼ぶ$\mathbb{F}_{2}$係数正方行列$\mathbf{A}$を導入する：

\vec{x}_{n+p} =\vec{x}_{n+q} + \vec{x}_{n} \mathbf{A}

Twister行列 $\mathbf{A}$は，桁間の情報を混ぜるような処理をしている．

⇒ GFSRより長周期: $2^{wp} − 1$が達成可能(w:ワード長)

行列$\mathbf{A}$は次のようなものを選ぶ．

\mathbf{A}_{w\times w} = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ 0 & 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \cdots & 1 \\ a_{w-1} & a_{w-2} & \cdots & \cdots & a_{0} \\ \end{pmatrix}

$\vec{x}\mathbf{A}$は行列積の計算だが，実際はシフト演算と足し算になる．

\begin{eqnarray} \vec{x}\mathbf{A} &=& (x_{0}a_{w-1}, x_{w-1}+x_{0}a_{w-2}, x_{w-2}+x_{0}a_{w-3}, \cdots , x_{1}+x_{0}a_{0} ) \\ &=& \left\{ \begin{array}{l} \text{shift right}(\vec{x})=\frac{\vec{x}}{2}, (\text{if LSB of } \vec{x} == 0)\\ \text{shift right}(\vec{x}) + \vec{a}=\frac{\vec{x}}{2} + \vec{a}, (\text{if LSB of } \vec{x} == 1)\\ \end{array} \right. \end{eqnarray}

seedの$\vec{x}$をそのまま使うわけでなく，奇数か偶数かで定数ベクトルを足す，判定に使った情報(LSB)は削除($\vec{x}/2$)するので攪拌され，seed依存性が薄れる．

後処理 Tempering Transform(焼き戻し変換)

最後に後処理として，

  • 高次元均等分布性を改善するために， Tempering Transform(焼き戻し変換)$\vec{x}_{n}\mathbf{T}$ を出力

（今回は省略）

参考: - (松本-栗田良春1994) - http://www.thothchildren.com/chapter/5bdece8c41f88f267247fcf6

Mersenne Twister法

JIS規格Z9031 5.4.5節で示されている．

Twisted GFSRの周期を$2^{wp − r} − 1$ の形にするため、 状態空間wpビット中r次元を「使わない」ように拡張．

$w,p,r$の選び方によって，周期をメルセンヌ素数になるよう調整できるようになった．

\begin{eqnarray} \vec{x}_{k+p} &=& \vec{x}_{k+q} +\vec{x}_{k+1}\mathbf{B} +\vec{x}_{k}\mathbf{C} \\ &=& \vec{x}_{k+q} + (\vec{x}_{k}^{upper(w-r)} | \vec{x}_{k+1}^{lower(r)})\mathbf{A} \\ \end{eqnarray}

記号：

  • $w$: machine words of size, bit数, ex.32bit
  • r: 下位lower r bitsで分割．ex. r=31
  • $\vec{x} = (x_{w-1}, x_{w-2}, \cdots , x_{0})$: word 例えば32bitの値 0xffffffff
  • $\vec{x}^{upper} = (x_{w-1} , \cdots, x_{r})$: w-r bit, ex. w-r=32-31=1bit, $\vec{x}^{upper}=(x_{31},0,\cdots, 0)$
  • $\vec{x}^{lower} = (x_{r-1} , \cdots, x_{0})$: r bit, ex. r=31bit: $\vec{x}^{lower}=(0, x_{30}, \cdots , x_{0})$

$2^{n }-1$の形の素数をメルセンヌ素数、 そのときの$n$をメルセンヌ指数という。

現在48個知られており、 19937は24番目のメルセンヌ指数.

メリット：

短所:

  • 暗号論的擬似乱数生成器 (CSPRNG) ではない。（次に生成される乱数値が予測可能）
  • 内部ベクトルが大きい

MT19937

記号と漸化式が以下になるときのメルセンヌ・ツイスタを 特にMT19937と呼ぶ．

$w=32, r=31, w-r=1, n=624, q = 397$

\vec{x}_{k+624} = \vec{x}_{k+397} + (\vec{x}_{k}^{upper(1)} | \vec{x}_{k+1}^{lower(31)})\mathbf{A} , (k=0,1,\cdots)\\

k=0のとき:

\vec{x}_{624} = \vec{x}_{0}^{new} = \vec{x}_{397} + (\vec{x}_{0}^{upper(1)} | \vec{x}_{1}^{lower(31)})\mathbf{A} \\

周期を計算する．

n=624
w=32
r=31

p=n*w-r
p
> 19937

特徴：

  • 周期が高周期：$2^{19937} − 1 \fallingdotseq 4.3 \times 10^{6001}$

  • 1周期で（32bit精度で）623次元空間に均等分布することが証明されている．

簡易な実装

※実際に使う場合はライブラリをそのまま使ったほうがいいい．

参考：

pythonのrandomモジュールではC言語でそのまま実装されている．

流れ：

  1. seedを決める．
  2. seedからn=624次元の内部ベクトルを非線形式を使って初期化(Knuth TAOCP Vol2. 3rd Ed. P.106)．
  3. 漸化式でn=624次元の内部ベクトルを更新．
  4. 順番に乱数として出力．

初期化:

/* initializes mt[N] with a seed */
void init_genrand(unsigned long s){
    mt[0]= s & 0xffffffffUL;
    for (mti=1; mti<N; mti++) {
        mt[mti] =
        (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
        /* In the previous versions, MSBs of the seed affect   */
        /* only MSBs of the array mt[].                        */
        /* 2002/01/09 modified by Makoto Matsumoto             */
        mt[mti] &= 0xffffffffUL;
        /* for >32 bit machines */
    }
 }

pythonで書き直してみる．

# 初期化
N = 624
M = 397
mt = []
mt_i = N+1

#initializes mt[N] with a seed
def init_genrand(seed):
    global mt
    mt = [0]*N
    mt[0] = seed & 0xffffffff
    for i in range(1, N):
        """
        /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
        /* In the previous versions, MSBs of the seed affect   */
        /* only MSBs of the array mt[].                        */
        /* 2002/01/09 modified by Makoto Matsumoto             */
        """
        mt[i] = (1812433253 * (mt[i-1] ^ (mt[i-1] >> 30)) + i)
        # for >32 bit machines
        mt[i] &= 0xffffffff

    global mt_i
    mt_i = N

seed=0x00000001
init_genrand(seed)
len(mt), mt

> (624,
 [1,
  1812433254,
  3713160357,
  3109174145,
  64984499,
  3392658084,
  446538473,
  2629760756,
  2453345558,
  1394803949,
  1021787430,
  2063496713,
  1304877364,
  1713639158,
  889001601,
  1651239412,
  1450863289,
  745575081,
  361057727,
  2288771950,
  1463387568,
  2249488362,
  26637982,
  204036717,
  1655702041,
  1329048465,
  2092351466,
  1681619666,
  3220660315,
  1301783610,
  626286181,
  294669048,
  3537128440,
  3259518248,
  2550101273,
  1160881866,
  308703547,
  295714668,
  35508674,
  1599247281,
  376272024,
  3166459937,
  1852735737,
  3680868867,
  612352556,
  2760189833,
  3816750341,
  699140493,
  1087846865,
  394927937,
  2063539671,
  645417889,
  2337669049,
  3773167612,
  678121169,
  3006984620,
  1163491294,
  2559287860,
  543155592,
  3194181347,
  2463543297,
  3875146860,
  475483913,
  3707568076,
  3881808875,
  1264657097,
  208126250,
  1802809301,
  367907560,
  2433375693,
  2851326449,
  2380707878,
  2911758972,
  4243386879,
  2229228726,
  828161871,
  2871116151,
  990638198,
  178193628,
  1012573979,
  1223581943,
  3333023583,
  1901888414,
  3913876750,
  3168662389,
  656194888,
  1553610174,
  466840498,
  686407570,
  280737523,
  2476489017,
  1272981410,
  3189431979,
  3294710282,
  1564477163,
  4133221553,
  823708826,
  880616227,
  1730254897,
  335723347,
  2123911971,
  344194767,
  119099153,
  2915257116,
  3339825470,
  2524942970,
  1191117250,
  3403812186,
  3988972937,
  2575395295,
  4072737183,
  663832315,
  808080503,
  724042340,
  2966189542,
  2499643239,
  3309205581,
  1915303227,
  72616536,
  387525935,
  2791701251,
  2190905566,
  3740328774,
  831297460,
  3750964864,
  2190112044,
  899144100,
  2346558003,
  3851695829,
  2896963823,
  1548614403,
  3676707405,
  2050891594,
  4165893148,
  1883017153,
  2668787527,
  50330561,
  2063572142,
  1853585557,
  1716111087,
  2937248370,
  1650859709,
  2682305722,
  565243175,
  3922227187,
  3482032705,
  2809081500,
  2099376873,
  230358556,
  1065827745,
  196966939,
  3268845630,
  3625508265,
  1477799595,
  4149453740,
  2757835686,
  3032697936,
  2200108791,
  3421680711,
  4145382259,
  3605253072,
  1186485728,
  3520482151,
  3080733463,
  3887314157,
  4030447755,
  1699987022,
  1393253586,
  1710066407,
  710337383,
  3754612557,
  2741088369,
  337455371,
  1304761604,
  3592681639,
  3099385187,
  4003676405,
  317081535,
  997754381,
  480565460,
  3806265432,
  1068029852,
  776179010,
  470617537,
  3653875421,
  2273571919,
  1055365147,
  1317172834,
  3414733003,
  2835400613,
  28845217,
  631741764,
  2334552212,
  3565466095,
  1225096926,
  1277781438,
  2416008223,
  1268768054,
  2750789241,
  267768398,
  2175383438,
  268654341,
  2550530755,
  2971623408,
  1666669894,
  1934871760,
  509782083,
  2798468670,
  2834016892,
  2494149255,
  1965005899,
  2653045765,
  2317194903,
  1297426078,
  916214929,
  2967861004,
  2236807006,
  2476725285,
  128488253,
  4277714156,
  3016192551,
  1690883702,
  1329810641,
  593010415,
  2341313579,
  1754238478,
  1242698701,
  2152594527,
  2103269013,
  926178633,
  647225267,
  4243787142,
  1489208161,
  3188798921,
  1327553793,
  3644600811,
  684513652,
  2606555057,
  2705329549,
  2557469018,
  1294205096,
  70104222,
  3020083528,
  2015571237,
  2768573480,
  401698695,
  2812362809,
  328919870,
  984940142,
  1653817439,
  471643152,
  538942283,
  2040555667,
  1211982999,
  1663497772,
  2941793728,
  3001026698,
  313271977,
  3644502703,
  2423950047,
  2629046069,
  3450826936,
  44600781,
  2633869288,
  4267014746,
  4204914470,
  1955987363,
  2590608885,
  2120168063,
  1460034243,
  258056600,
  3693550087,
  779446436,
  902696389,
  4228701387,
  3165791227,
  3478614865,
  1500865135,
  905884796,
  3682046467,
  2437847832,
  2595888219,
  4144484663,
  1299603103,
  648536946,
  1762836247,
  4265749196,
  950840266,
  2928992722,
  2051369009,
  2071186450,
  1164619682,
  210405235,
  1296628868,
  2425474719,
  4083386904,
  1978331343,
  3190898799,
  602128683,
  2003319330,
  1043377147,
  756690484,
  24776626,
  1835824233,
  1156421176,
  2125448878,
  1333136189,
  607751135,
  4255614767,
  4238533009,
  2583175632,
  230472465,
  3037259757,
  1546348932,
  2537279411,
  110471952,
  520621708,
  63613561,
  2843673595,
  775036,
  1899744556,
  1168115970,
  2685086321,
  3410250658,
  3151102153,
  634647644,
  3639125394,
  3344624764,
  1525171811,
  1878800371,
  3356530116,
  3676542926,
  602053165,
  2686708238,
  3703555082,
  3754961372,
  3970030923,
  1749014201,
  3391107050,
  2478152000,
  2121779806,
  2636689360,
  769835312,
  4230539591,
  1909812524,
  417081626,
  3096519324,
  387659697,
  3764499249,
  3452925463,
  3818277698,
  3008920324,
  15253694,
  1479260759,
  2421328720,
  2220743357,
  38831551,
  1032912064,
  3400956198,
  2362808832,
  3988706866,
  1950464958,
  3248573125,
  1225815945,
  1211036180,
  346407094,
  3867176764,
  1257086026,
  2725236231,
  2843735658,
  4147241082,
  1729974832,
  1256499145,
  3765975901,
  784776076,
  4288277427,
  3903532520,
  3431522864,
  2792589977,
  2935989154,
  3536596892,
  3512984120,
  605476293,
  1774961976,
  981422589,
  822525778,
  3343539932,
  422954622,
  1323482938,
  2523465420,
  2746609356,
  1664448205,
  272567300,
  711582493,
  3625722107,
  3615865699,
  950619756,
  2864168489,
  108006277,
  3976313352,
  680217319,
  173747636,
  291134870,
  198587329,
  595310009,
  941470866,
  2438488368,
  1681923153,
  1654783272,
  3531789254,
  4149541715,
  2922706987,
  684907209,
  3116688362,
  3288142886,
  3953377592,
  3332428007,
  1400401813,
  3745921798,
  1701705628,
  3744511893,
  1838265811,
  3314032512,
  3894840150,
  3810031409,
  181324387,
  983160249,
  1444959400,
  3836664153,
  3032673327,
  310789231,
  3701565562,
  1407580781,
  2511575629,
  3113822685,
  1777261998,
  2208898751,
  106383174,
  2961020500,
  995776421,
  3306087121,
  2181030035,
  2300064751,
  1909543740,
  4023156173,
  1671619075,
  2151956104,
  237668401,
  3204511253,
  1303668692,
  3868259787,
  2737897899,
  4091026033,
  2877780671,
  134376279,
  398912026,
  863520778,
  3712468923,
  3443213666,
  2183809552,
  2597379302,
  349776833,
  274697715,
  4266593710,
  4282186769,
  3530757867,
  520237914,
  3369037397,
  2285670338,
  387086485,
  618942879,
  219892882,
  2008897906,
  2293749560,
  2907436476,
  3853296593,
  327550390,
  1558751403,
  2125694704,
  1822570484,
  2409968265,
  436622776,
  2691124090,
  1080819771,
  2958107334,
  2667158841,
  2117901613,
  440045635,
  3861104471,
  3574962701,
  3210299248,
  1368601573,
  2434039520,
  86704919,
  3628108033,
  1909858745,
  227461000,
  2530509465,
  838433817,
  730224848,
  1060658180,
  1318482825,
  233266846,
  2352800845,
  2086493219,
  3826355555,
  3174377690,
  1455208243,
  1356597942,
  663563056,
  2501819374,
  4213535259,
  1585241464,
  873997246,
  2597898744,
  427064229,
  1587746589,
  259660817,
  1688808891,
  4165834345,
  1359025114,
  2013923952,
  2963511711,
  2903220732,
  356112706,
  501549847,
  1609412897,
  1685128111,
  2639303606,
  700554261,
  914150235,
  2010650618,
  2029243163,
  3046509911,
  715702687,
  2206956754,
  3045298216,
  2922667179,
  2497577415,
  3001819604,
  706666890,
  2275923855,
  3094184383,
  2781697712,
  3292952666,
  4238614078,
  278500659,
  1440033346,
  1552714131,
  336554687,
  2842580609,
  2255044310,
  2180071372,
  99970159,
  2078552309,
  1172694639,
  1359399314,
  546452524,
  349053834,
  3072254369,
  3043246719,
  3314426498,
  1594992663,
  3582269665,
  2114045278,
  585873328,
  840739494,
  3475778485,
  1506518790,
  4008486652,
  229989333,
  3582278212,
  363921215,
  3592842520,
  1833533669,
  708173875,
  564248927,
  853943228,
  2282731374,
  2874158047,
  3978663285,
  2332696531,
  1354524859,
  58121641,
  1445193461,
  1936635021,
  3374328198,
  3465253060,
  385589199,
  1819596280,
  912895627,
  1877426726,
  733280947,
  2004202992,
  3311780711,
  3732053191,
  309903272,
  97290141,
  2945419335,
  3916477072,
  1326195031,
  3740938055,
  3604745262,
  3633308956,
  3392929431,
  1257547457,
  251825182,
  3318700085,
  847033774,
  137350663,
  1716455973,
  546850455,
  4227574519,
  3044214953,
  2259874013,
  2442748258,
  2956971336,
  2198772379,
  1269686727,
  2648116105,
  1339159363,
  1473334647,
  2386671612,
  2069268389])

ここの処理で，初期化された内部ベクトル（n=624次元）から漸化式で乱数を生成する．

\vec{x}_{k+624} = \vec{x}_{k+397} \oplus (\vec{x}_{k}^{upper(1)} | \vec{x}_{k+1}^{lower(31)})\mathbf{A} , (k=0,1,\cdots)\\

Cでの実装では以下のようになっている． Temperingは後処理なので今回は無視してpythonで書き直してみる．

/* generates a random number on [0,0xffffffff]-interval */
 unsigned long genrand_int32(void){
    unsigned long y;
    static unsigned long mag01[2]={0x0UL, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= N) { /* generate N words at one time */
        int kk;

        /* if init_genrand() has not been called, */
        if (mti == N+1)
            init_genrand(5489UL); /* a default initial seed is used */

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

        mti = 0;
    }

    y = mt[mti++];

    /* Tempering */
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
 }

MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000 # /* most significant w-r=32-31=1bits */
LOWER_MASK = 0x7fffffff # /* least significant r=31bits */

# generates a random number on [0,0xffffffff]-interval */
def genrand_int32():
    # mag01[x] = x * MATRIX_A  for x=0,1 */
    mag01 = [0x0, MATRIX_A]

    global mt_i
    if mt_i >= N:
        # generate N words at one time
        if mt_i >= N+1:
            # if init_genrand() has not been called, */
            default_seed = 5489
            # a default initial seed is used */
            init_genrand(default_seed)

        y=0
        for k in range(0, N-M):
            y = (mt[k]&UPPER_MASK)|(mt[k+1]&LOWER_MASK)
            mt[k] = mt[k+M] ^ (y >> 1) ^ mag01[y & 0x1]

        for k in range(N-M, N-1):
            y = (mt[k]&UPPER_MASK)|(mt[k+1]&LOWER_MASK)
            mt[k] = mt[k+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1]

        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK)
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1]

        mt_i = 0

    print(mt)
    print()
    y = mt[mt_i]
    mt_i += 1

    # /* Tempering */
#     y ^= (y >> 11)
#     y ^= (y << 7) & 0x9d2c5680
#     y ^= (y << 15) & 0xefc60000
#     y ^= (y >> 18)

    return y

乱数生成関数を実行する．

genrand_int32()

[2629073562, 2983301384, 681580311, 4033622241, 792772838, 3306961981, 92883131, 1785085746, 3364128315, 2402025379, 3224868746, 1145213362, 3784365245, 1948434636, 2667646161, 2598854474, 921967201, 1345782310, 4019597455, 2906395199, 1349669984, 2676817993, 4201769589, 2002781766, 3540177092, 4224925813, 3661313599, 1709930435, 1812273278, 2973452884, 1592291796, 3452239013, 3588672187, 3228651068, 3191454495, 3286135343, 2640545275, 3096953148, 3746505897, 2292163827, 2164382601, 1581410039, 2413832827, 2536571847, 179684232, 1638923698, 3155158821, 1454330362, 4050607484, 607322300, 2216566078, 597866774, 1036426282, 732815996, 3131865469, 2440339870, 2814550949, 1479383443, 2449469876, 3810238677, 2923086221, 437801529, 2891199990, 1886893516, 3898673786, 376204646, 1392372379, 4123661669, 1140754642, 3539167101, 2386309702, 3740957436, 4033654965, 1720449988, 3434980330, 4213508374, 3576835843, 2818865106, 1653162115, 2935588114, 3870616539, 102614847, 1476834675, 1220770796, 1233652508, 2385138085, 1300608482, 2753953039, 262993567, 4009374062, 2143978386, 1613109469, 3072671496, 1223816410, 4088822114, 3382188205, 2250056281, 1926821318, 3806317775, 2882166470, 94227745, 2877123406, 1030225246, 1555072155, 95009460, 1855512191, 2840453856, 2478087736, 836340051, 1566383306, 2625414289, 3519123538, 840509954, 2373484829, 676528503, 2783662465, 3557034492, 2566048980, 2347785709, 3566819907, 1311855742, 198269976, 2693520819, 2127070362, 961491174, 3932714317, 837664826, 4277891831, 3535515583, 2831416447, 3505045078, 3763313683, 367436315, 3614057572, 3780746374, 2693039652, 2297021184, 2224934154, 698822522, 2718629137, 1175446314, 2603507610, 2067589016, 2280810156, 2037033584, 3956938481, 1112874779, 3264939860, 2054107185, 2354026721, 1958640221, 2844284824, 3775753525, 2462549847, 3562644229, 3683686884, 3714884555, 2266356233, 2808583945, 980888698, 1137581788, 2771236582, 1975939317, 1605707990, 614167064, 767063856, 4227905160, 3590303986, 2932373212, 2230415839, 127157074, 2328724316, 3356372094, 3215726425, 282321962, 4226412442, 106823192, 3925701436, 610765913, 281952627, 1832011890, 2670621135, 1012800992, 1489632964, 1371755819, 2529629289, 607643288, 3941535311, 3202770816, 284461833, 3696778854, 325625733, 2671656400, 1391137252, 1240723705, 3132941411, 314202987, 1301784708, 2575857120, 313287791, 3569720512, 981744121, 2986286440, 1051168756, 3881027887, 1088809168, 3421075971, 2655923113, 2577977181, 3968201444, 1406585576, 4001025594, 1854233928, 3825832114, 954907921, 3109212504, 1706316388, 1550715292, 2934259476, 1892992132, 4050317728, 4110743408, 359920673, 3542060425, 597068400, 843058885, 3799566677, 2064802063, 860032883, 2732673041, 3457529378, 3660165513, 1125914118, 4212233956, 3757086488, 2632116865, 462233764, 161423763, 141910303, 2265109737, 1983126147, 2231395445, 2147383559, 611750005, 2194081082, 1699618892, 3841025952, 1294478167, 936120505, 4102008957, 4268194620, 1994019922, 1187332833, 3953675561, 1917283619, 896867387, 1634068959, 3950876764, 485558549, 45383166, 2795959904, 1717914918, 3449856475, 3796449494, 3318166191, 1007512487, 480498390, 1730605673, 3972660041, 2287008439, 539639323, 1569683418, 3795864463, 453065119, 2449404120, 265049099, 3514892628, 2665563904, 2534523080, 1969344934, 4294466702, 1478959417, 1858551310, 3029422620, 4121720519, 2933843154, 3209557296, 3111170404, 4264711934, 2448282623, 1388503581, 1999436060, 818418468, 3283991819, 2356924521, 2684567658, 1424193429, 1187340812, 3847120877, 1987859863, 1879502046, 3422594099, 1419478013, 4148487199, 2538837125, 3694851522, 636350498, 1097832595, 3779331880, 351970715, 2534774459, 3389311029, 3762283879, 3742425828, 3882821767, 2683353, 1981273229, 4068324016, 539226467, 2411256222, 1780609115, 2059099269, 2889497980, 1123848930, 540086248, 3467353606, 3362203896, 4058078927, 93044840, 426751932, 824266620, 3444590461, 2122918776, 3339845861, 4233923286, 3733051177, 2957657929, 3110908772, 2551930098, 1294126893, 2213336821, 2124571119, 49780221, 2901327722, 2493306969, 2545470627, 102527300, 3876142393, 4097726412, 3510695954, 660912408, 2033930425, 1601509561, 969180562, 635252598, 177954239, 3054207519, 4122051269, 2787463443, 1664731394, 2907371963, 1484884283, 1560546623, 2902374922, 2395942225, 451352804, 3346805556, 3459298550, 3482428591, 10753957, 4101820340, 3306178891, 1122941824, 355877597, 1683964498, 238724805, 3926649337, 3197046734, 4277634633, 2288745211, 4202067531, 526022968, 4017453944, 1499184106, 2677441952, 2227353703, 1995296581, 1690255681, 2920887680, 605849491, 3072795503, 746910746, 2709796449, 1225135658, 657841564, 4070363626, 144842260, 3718575695, 3159187032, 88291794, 3129049475, 410962657, 1728726693, 2397606939, 4126386549, 751549633, 4226219908, 1549973222, 3060733996, 3741110422, 2530947598, 2627897488, 2317706652, 1170828427, 2671701715, 1153351468, 3762293788, 4093330405, 1641962571, 699324101, 3173743570, 1798831929, 3467616712, 4198420524, 2448981354, 499920867, 968642107, 2140815539, 4193124145, 1639223168, 284638153, 396985542, 3543438633, 237854258, 3938010494, 24441053, 2947436871, 1273496002, 719279415, 3574242559, 1040109604, 3849196601, 3250223302, 3411729501, 3031943234, 2932285520, 2932420675, 2011314805, 2480850074, 3207806491, 462404995, 3279042455, 4270524229, 1064389665, 1894847490, 721365878, 357178131, 2827490451, 2604438657, 242514037, 678802395, 1322770750, 2747624534, 4246466163, 4188936761, 1207204018, 980275996, 841637218, 1468131552, 4102349079, 586888764, 3105466755, 1628818384, 2991889790, 2801191520, 2114916962, 1124291831, 3242113092, 1082871720, 3625937786, 2796251125, 1651820702, 3427511545, 2035120316, 1024058911, 4209506140, 2527167744, 213886228, 2514956543, 2450260579, 327684603, 3444379103, 3884997363, 2844468873, 2261078634, 3926825101, 439487268, 3789435080, 1212963762, 4259079565, 2772611204, 2534236055, 2430244594, 916922266, 903950702, 3381351589, 2268543712, 3616954837, 1273083041, 1682465785, 1342921678, 2593265787, 3033724173, 2988544460, 1824668777, 1214999983, 257453352, 4187931679, 3523379959, 1481153225, 4290295859, 220376185, 4136013972, 511679284, 3510589272, 1404047266, 3712771231, 2125374725, 32037606, 3601685135, 3433623522, 841138647, 1610171318, 3920699442, 1084892922, 3146108732, 3672652561, 1148331655, 2473777375, 3039860130, 1170979324, 575756423, 1389255297, 339011744, 2351938991, 4050094885, 2773634239, 3715040333, 3920910597, 562407139, 29887881, 1623822350, 358193390, 1822261341, 1243290919, 755541153, 153529770, 994467513, 1339524978, 3174283928, 2782204324, 182251010, 1833692038, 3477775846, 2820237500, 2165639585, 4089211432, 4010345846, 1238643345, 3710224584, 2251039304, 1196168985, 3165387311, 3920626153, 1796963839, 2112227260, 3358845388, 593715887, 3046897033, 2968478428, 3846781604, 3565923316, 2452128692, 68338106, 1427007580, 2192917968, 75235680, 2134869635, 1857807303, 3745016485, 2601327385, 35512535, 559792668, 2093376088, 939608650, 2259549051, 2605376692, 2058599240, 2980581379, 3160415220, 2739135905, 254886981, 1652380747, 371107437, 1123937393, 4185309254, 864314942, 2739416220, 2185572068, 1163546293, 3491702910, 996401156, 1198755052, 2898003956, 745796080, 4127642404, 4237523457, 1274635091, 3144139009, 1600421663, 4226154574, 538248802, 373236455, 116925273]

2629073562