#P1362. 骨牌铺方格

骨牌铺方格

题目描述

有1×n(n<=50)的一个长方形,用一个1×1、1×2和1×3的骨牌铺满方格,请问有多少种铺法?

例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格,共有四种铺法。如下图:

![](http://oj.czos.cn:443/admin/../data:image/png;base64iVBORw0KGgoAAAANSUhEUgAAAhQAAAAuCAIAAAD/ZhdQAAAgAElEQVR4nO2dezxU+f/Hz7iWGWNccrdIpM0vqy25tbkmRTfFWkVXKdWmRCSV2kshdNFFbW02oQ1JfdtaSrpKRbqJRBfJLQwzGDPn98f74TxOczN0tGN3nn94HGfOfOZzPudzPq/P+/35fN4fBJUgQYIECRL6CfJPZ0CCBAkSJAw9JOIhQYIECRL6jUQ8JEiQIEFCv5GIhwQJQw82m81ms3t6euAvHBCePp6enh4Oh/M5aXI4HEjqM9P5AnyBHHI4nM7Ozs7OTuzfbhHo7Ozs6upiMBgMBgOOOzs7mUxmV1cXHGN/q6qqMjMzs7KyCgsLr169evbs2aysrOzs7Ozs7KysLDjGn8zOzs7MzMzIyMjIyDhz5kxGRkZWVta5c+eampqggvHegkQ8JEgYenA4HBaLxWKxoC2GAwLTB7XAfmuQUhZbenp66HR6U1NTU1PT3bt3MzMzi4uL09PT9+7dux/HgQMHEhMT4+Pj9+3bl5iYCJ/Gx8fHxsbGx8cnJibu2bNnz549cXFxcXFxsbGxcXFx+/bt279/f2BgoIuLy9ixY83MzJYuXfr999/PmTPHrC/GjRs3ZswYU1PTsWPHGhsbGxkZmZiYjBkzxsjIaOLEiePHjzcyMjIyMho1apSJiQmNRkP6j4yMDJVKVVRUlJWVhTPR0dFsNru7u5u3lCTiIUGCBP68efPm48ePHA6nqqqqoqKikh9w/sWLFxUVFRUVFeWCqaioqKqqYjAY4m95oCgaHh6upqamoqIiLS0NraqgBhcuwBgxYoSmpqaqqqqsrKy6uvqIESPU1NTU1NQ0NTU1NDTgGvhXS0tLU1NTXV1dS0tLS0tLXSgaGhrq6urW1tagE8uXLw8PD9+wYYO3t/fq1ashzZCQkLCwsE2bNoWGhkZGRm7bti0qKmrLli1bt27d9ilbt27dunXr77/HhsbGxUVBVeePHmysLCwurr61atXJSUlAQEBCIIEBQWhKMrXXvxPiweHwxFSj+Ejca7oWN44nwGWAlf94L2gX0XxJcuNK6viBmSssrKysLDw5s2bN2/evIEDO3Pt2rXr168XFBRcu3bt2rVrBQUF2DEXV69e/fvvv/Py8vLy8jZt2uTv7799+/alS5f68cPf39/Pz8/b29vb29tTKPPmzYO/CxYsWLp0qY+PD41GMzExmTp1qoyMjJSUlJCmU05OjkQiSUtLUygUMpmswAOZTCaTydra2o8ePfqnH4hILFq0yNDQcP/+/UlJSYcPH4a/yZ9y6NChK1euFBUVHTlyBM6cOHGioaGhtbW1rq7u3r17Hz9+bMVRX18/fvx4Dw+PxsZGOp3e1tYG51taWlpaWtra2uiCaWtra2lpYbPZLBarq6sLn1U2m02lUhcuXEhsCZSWliIIsmbNGlTA6/zfFQ8Wi4U5i/m2qvApi8USz1ZJ/G1/FEWZTGZHR0dHRweTyWQwGB0dHQwGo729HTvDZDLhGjqdDid5aW1tffbsWUdHR11dXWZmZnp6+unTp8E5m5qaeu/eve7ubsKd/kQBXv66ujozMzPhHgM5OTn4q6ysTKVS5eTk5OXloS3mhUKhwEciOSMQxmlCwszMzMXFxUkwLi4uLi4u06ZN09PTQxBk7Nixs2fPnj59uouLyyx+zJw5c/78+SEhIbNmzdq1a1dQUNDGjRvPnTt39uzZbB5ycnKio6MpFMr9+/f/6WciEv7+/m5ubsSmyeFwxo8fv3nzZgITRFG0sbGRRqOdPn0a7W3WCEn2+vXrEvH4LLq7u8VTPNhsdltbW0NDQ3Nz80cczc3Nzc3N4K7FHwuivr4+JSVl9+7dmZmZBw4cAF9tQkJCfHx8XFxcfHx8TExMTEzMrl27fv75559/vkX0di9e3dYWJi5ufno0aNNTU3HjRs3fvz4MWPGgEPW1NR01KhR+vr68K+hoaGhoaGBgcFX/NDT06NQKPr6+pqamrzNopGRUVNTE4qi4inzkKWXL1/Kycnp6+sHBQUFBQWt+pTAwMB169adP3/+4MGD58+fLy4uLi4uzsrKys3NLSoqusePoqKiBw8eJCYmIggSGBj46NGjBw8ePOTHgwcPSkpK6HR6S0uLiHn+9ddfEQQ5c+YMsUVx69YtZWXlBw8eEJvsILFo0SJnZ2dia1RXV5eFhUVISAhRCWLiQaVSN23aBF2oz+9FScSjD5qamh4/fvz06dPnz58/4+H58+ePHz+ur68X28khL1++tLS0pFKpXM4B6JAqKirCwBf+gC8UCkWUriuJRNLR0dEUGS0tLT09PWj9DQwMoI/81VdfOTs76+np6ejoODk5RUVFOTg4TJw4MTw8PCoqCvyzvERFRW3fvj0yMnLr1q07duzYuXPnjh07QMnmzZunrKxcX1+PoqjYWh4oilZVVQ0fPtzT05PYxC9duoQgyNatW4lNNikpiUQipaWliXIxvCBdXV3gUWGxWN3d3bzWPIqieXl5KioqDx8+JDa3g8QQEo+mpiYymWxjY9PZ2flPigf2pHmd4KLAZrPfvn3b09Pz7t27R48e5efng2f2Ko6/77ypUr+fn5V65c+euvvy73xZUrV3JzcwMCAtasWXP06NEFCxb4+vr6+vp+3wv4dj09PcGUFoXZs2ePHj26TzfC6tWrxVM5UBTNy8tDEERNTc3W1tba2tra2trKymr69OkRERF+fn4HDx5MTk6Ojo6Ojo5O7ovjx4+fPHkS/i5cuFBZWfnIkSOnT5++du1aSkrKjRs3CgsLb9261d4fwFELxx0dHStXrkQQJD8/H0XRjo6O9vZ27EZYLNaACyEzM5NGozU0NBBQoINJY2OjqanpjBkzhFQn/HsH77+QgRxwTdy6dYtCoYSHhwu5WPQXGVp/FEXz8/NlZWVPnTqFCmg1MEnAZvGCt0T44FNeXp6ysnJJSUmfOREHhpB4NDY2KigoODg4EOUmwcQeQZC1a9eiIooH9CD+/PNPR0fHSZMmffvtt+PHj7cQmW+++UZTU9PCwkJbWxt8uFxISUnJysrC1AXoICsqKvIOr3GB9Y6HDRsmqK23sbHx8PCYLhpubm6zZs2aLxhPT08KhWJtbc1kMj/YQwGV69eVVRUzMrKwt5hQrreJ06cUFFRefPmzecnhQfE486dO0QlCLX5999/p9FojY2NRCU7SFRXV1MoFA8PD6LMIxCPmpoafX39TZs2oUTMUOBwOOD6q6mpoVKpwsUDNAOMDGytifD0L1++rKqqWlpa+pn5/DIMLfFQUlIC8SAkWXB/PX78WF1dffXq1ajolgebzfb29kYQxmlCYsGCBStWrAjoD6tWrYK/a9euXbdu3Y8/rhu3brg4OCQkJDvvvuOTCanpaXl5ORs3Ljx5s2bDx8+LOkLzG9bWlr68OHDsrKyx708efLk2bNnnp6ekydPJryVd3R0VFVVBX+6GFJQUKCqqsrVj4NxfuhCwuzs/vbrk5KS1NTUXr16RWReUfTw4cPDhw8vLCwkKsGhJR6VlZXS0tIzZ84kSjzg+dbX15uYmISFhaEETW8D66Guro5GowkRj4GRl5dHo9EIrAODypAQD2yh6JIlS2xsbAgUD1h1OGXKlMDAQLRfYx5eXl4zZswgKisYR44cMTAwwBZVEkVAQICrqyuxaaIoun/fjU1NfCniyEFBQU0Gu327dv4k9iIGfQEecWjzymtBw8epFAoBQUFROUTfu7s2bMKCgrXr18nNlnxFw8o8IaGBhMTkxkzZhAlHuCJYjAY33zzTWhoKEqQ5QHWw/v37wWJB77+lJWVxcTEBAcHr1+/Pjg4OCcnp7y8HH8ZV2XLz89XUFAQcSjlH2cwxKOzs9PCwgIsRULAfJILFy4kVjzYbHZnZ6ednd1AxGPu3LmE5ANPQkKCrq5ua2srsckuWbLEycmJ8PHS48ePi7PlUVhYqKSkVFRUxPdTzCWNzUiGpgFmtQoJNXH48GEEQRITE4nKJzb4RqVSCdck8RcPeLffvn2rpqZGoNsKYDKZ48aNI0o8MOrr6/mKB4xtoChaU1Pj6+urpKTENaWCSqVGR0fX1dWhKAoj5/jmDCyPJ0+eEJXPQWUwxIPJZFpaWi5evJioBKGn2NTUpKSkZG9vT2x3n8ViDVA8Zs+eTWA+gKElHkePHh3S4iFkmFTIRyAeBw8eJCqf8EMPHz6k0Wj/TfFgs9nt7e0ODg7Tp08fuuLB4XCgbSooKLC2tgbB4FpcDUyZMqWmpgbt9a1hyebl5SkpKf1nxzzAUrS2tibWRADvgqenp52dnViIx7x58yTiIf7iQaPRBE18xB52c3PzxYsXt23btmzZsu3bt8fFxQkfz0hKShoM8bh/5/Uzwgn7W1tYaGhu7u7kNaPFAUffXqlampKciGrKysrKwsiUTCLA8ZGRmQEzs7u9evX6Ofzp8eWpaHv7+/s7MzgQmy2WwGg2FnZ6eqqir6mhsRCQ4OtrGxIbZ29Vs8wOkZGRk5f/583qsxZ4igmRXYgC3fHxMkHuBa4brz8vJyrtFgQc4WvuIB+URxt93W1nbnzp0NGzbs3Lnz7t277969g/P40KH49MVcPG7cuCEnJ7dv3z78SewBwd+EhARTU1Ps9QaUlJRmzpyJLfTlKreMjAwZGZmkpCSi8vkFxAPGpYj1MBBLT0+Pl5eXq6sr4WMe5ubmoosH5rEUfrEgt1Vra6uNjQ3MmSSRSFJSUnDA5byCQCb+/v7op7UrPz+fQqH89ddfA73pL8qSJUumTp0q6NM+y1AQkydPVlVVJTw8hI+Pj52d3cCyJOhe+i0e4NPctWuXj48P35/Bbru2tvbChQs7duyYOXPmunXrLly4gKmCoBifQsQDpgijKFpRUXHy5Elvb29tbW0qlerh4bF27drz5883NzejAhaC8RUPmGsE9/zs2bOwsDArKyssnIO8vPzo0aOXLVv28uVLtNf6w/IAiLl43Lx5E0GQpUuX4k+CVxpalrCwMEHTmhEE0dXV/fXXX3lXZWdnZ8vLyw8hy0NZWbmxsVGUqaL/LIsWLZo6dSqBU3XZbDadTu/XgDlU8j6DqwsSj/T0dEw5hFQtbPzj7t27+GTz8vJkZWVjY2MHeM9fll9++UVPT+/58+d8P4UONExJgr7v+/fvHzx40NbWduPGDYgCkJubm5OTc76X3Nzcs2fPmpmZKSsrp6enX7hw4bwInDt3Ljc3Nzk5OTg4eMWKFbCKAEKQYcyePVtBQUFTU3POnDlYgDJRmDt37sqVK9va2vjqR7/FAyr3zp07BYkHiqIfP37cs2fPuHHj8Cs5ZGRkpkyZkpqaCuu/+HrfBIkH9kYlJibq6+vjqyB2PHHiREH+fUHiAc1oWlraqFGjsHTk5OTwATJHjx598uRJyDDXEpshIR6rVq3CnwQV7Ozs3Lx5MxQgFlqZ692Ggz/++IMrWXBbDS3L49WrV+IchQzw8/MjUDwADoczfvx4WCRIICAeqampKK7VYLFYCxYsgDed71AHHnjFuHQiPz9fWlp6586dxOZ2kAgKCkIQ5ObNm7wfYU3tjh07Jk2aBMMYY8aM0dXVtbS0VFJSggi4fEsGzDXhpSfobRUC39dcFBQUFATF0eifeHA4HLA8Dh8+7Ovry7dMCwsL8SHeIJQmvjn+/vvvocHl/T1B4gFXxsbGQrGC8xTqqLS0NFbW+vr69+7dQ3nsLL4GJlywa9cu+K6UlBREBoUDGRkZWVlZSFleXv7YsWO8GR6i4oGiaGpqKlalBIWSBm/1yJEjnz59ik8BBsyFi8cA2uiysjJlZeXPmePPO2cURdGTJ0+SyWSYryye4UkwRBSP169fw1Y/r4VSU1Pz9u3bgoICTU3NVatW1dbWcl3wBgecefv27Y0bNx48eFBdXf3+/XshDxHEIz09HcW9awwGY+TIkQiCSEtL99mcwZs1f/58/Lz8q1evIggCjZH4s3z5cgRBuIwnAHOJe3p69ru1Fg1eZ6Cenp6KioqBgYG+vr4eDjhDIpHIZLKBgQEEiNMTDU1NTT8/PyaTyTeu6ADHPJKSknx8fLgWkaIoWl5eDhE3hVQgEolka2sLphCXg1XIgHlsbKwoZWpoaPjixQu89wxF0YCAAD09vRcvXnCl+eLFC8htn5DJ5KqqKq4yGnLiAUXd3Nw8efJkvlUQDwx4Igiybt06FBeMU/hsKyHDXcK5dOmSkpLSjRs3eD/6+PFjcXFxV1dXR0dHUVHR7du37+C4fft2bW0t5o7D3yyKoidOnFBTU4M9J8Q2ChnQp3jU19f7+PgoKipCT5YqFBqNpqysDAEXhg0bpqKiArF4ASUlJbhARUWFRqPRaDQKhUKj0YYNGyYnJzd8+HBXV1cmk4k1glw0NDRQqdQVK1ZgPhkOh/P8+XO+gSn5AuIxcuTIjx8/Ysnm5+cPHz4cNEn8CQwMRBCEax0VgFW2lJQUKysrS0vLqVOnent7W1paOjo6Lly4cP369YcOHTp48OChQ4fCw8MXLlx4+PDhQ4cOJSUlTZgwgUqlxsfHwwV8OXDgwOXLl48fP479m56e/u7du/v370Pw05aWFojlDscNDQ2Ojo5WVlZNTU2t/QEbtydmzAOahv/9739eXl5MJhMLdtbT08NgMHx8fKDdESQeUlJSYNJC2GH2p7tXChKPsrIyeA36NIcRBImIiOC6mVWrViEIwtswgeumTyMRLli/fj069MUDRdH8/Hx5eXlRvNJglFhYWNTW1mJ6LFw8QJ9evnwZERExY8YMD9GYM2eOsbExiUSys7ObNWsW/qNZs2ZNmjSJTCa7ubk5ODjIy8vL4gAb8cSJEyhP0Fxo9VJTU9XV1T98+ID1VAa1zD+HPsXj8ePHfVZ+QbW3T7A3Cx66vb19R0eHoEKDKK2enp4wQAIV4+LFiwoKCiLmCn7O0NAQP63o6tWrcnJy+/fvH6QSJpalS5eSSCS+AXVg1jJsqsFkMtvb26EYmUxmn9GlQkND1dXVCc/t2rVrbWxsiE1zgOJx8eJFW1vb2tpaEA8okTNnziC9/h9BrTx4scCGAhcTGC6QuCDxAOeSKL5UBEG0tbUrKyvxX4e4SVwukbq6Ol1dXUTkt0tTU7OsrAyfwpATD2D9+vWi3DXmxxs2bBgs/MaMTkSAeGAd1bi4OFGKlAtRXLd8AR8al8UD1nBFRYW5uTnMehjqlseHDx+Cg4NXrly5atUq3rDtXMBlAQEBWlpaEyZMWLt2LddXVq5cGRQUFBUVdezYsejo6Pz8/NjY2J9++qmoqOjWrVuPHj3q7OwUtAlKQ0MDjUaD/UexiSfNzc0i2vFIr2fCw8OD120FO9OJORwO56effho2bBhf8YAygfW2KC6iJfZdros5HA5sLY6iaFJSkoaGBt4g45t+Z2cnFDu2yJfFYnV2dmKGIPZbkIdVq1YRuHwEGOCA+ZUrV9TV1UtLS7Hcs9nsxYsXI71zLQBBbQRowM6dO0Gi+YoHZvoxmcxJkyYhIs/igJTxeQ4ICNDR0cFCIwAPHz6EjpIo4gHXwMg5hviLB4lE4hWPH374ARGhpcYG7uTl5WEcG7PEpaSkBIkH1NTffvvtq6++MhIZ2LpDTk5OV1d31KhRfC/45ptvfH19o6KidnxKdHQ0zNjm0gaoVOnp6fLy8lxDu+LJYAyYoyhqYWERGRk5gC/yzk3HqK+vV1ZWhv082L3B1dvb28eOHQtVS8Qxj59/hmf7LVr15BeN6mYw+FwoqOjZWVlBVkeXPP7MRcLb5FiBQiP/siRI+rq6sLFA7seS43rt7hygg6meKxcuRIVMKDIJzAiiqKXL192cnKqr6/HDNvGxkYtLa0+W2E8kydP7ujowP8wXjyw2VCFhYVUKlXENEGWFi1ahL+ZwMBABQUFrh3KduzYgfR62ISnic1M/+233/ApiLl4FBQUIPwsDz8/P6Q/3Xx5eXmwPKB2NjY26ujocC0fwYCXpL29vbm5GbbGFAU6nV5YWKimpnb58mXeb4EDl06n9+v2wYuVk5NDJpNhD7V/x4B5v+js7Bw3bhwERiQQsDz27NmDflqqYJVyTZARUq/y8/PxLemTJ0/U1dV/PFHYnM7SMB6eL5jHgMDiuLIkSMjRowQLh4DSHb16tXW1taEi8fkyZNBPPgaqQLFY9q0aU1NTdhQeX19vYqKiojtEWBlZUWn0/G/ymV5QDf2jz/+ED1NUILFixfj7wTcVrdu3cLfyMaNGxEEEbL3MgaM05BIpG3btuFTEHPxePr06YgRI3jnrixbtkyUviH+9mGbDXgcJSUlNBpNkGOa07s7b39zW1paqqKiwvWMuOhXsjAU9/HjR0NDQ7BEP2dfkC/AYIjHIK0wb2hooFAo7u7uXB78lpYWWF4uijU/b948bPYm0NTU9H/939Dwm2Foujt27dpNJrwGtsvhqJ4ODk5GRkZNTc3851bwV888vPzqVQqbBgJ3/nw4YOqqqqI7RFgZWXV3t7OO9sKxtAw8UhJSRE9Tai1XK18YGAgiUTimpGdlpYGs1H7tDywhbLHjx/HpyDm4oGi6NSpU7kWCaIomp6eLkrHEOm1TnR1dcHjB+/5sWPHSCSSkNlWnN5dH0QE6k9xcTGNRgMTh/cacOn2q/UHs7W1tXXUqFG7du1C/5OWx+CJh7KyckxMDP7lBZKTk/usUVCpIAwJvkMAPdmhIh63bt3qs7vTL4aieDg7O5PJ5A8fPqD8KphA8VBSUgJfM5wBS1akBr6Xb7/9lk6n438yISFBT0+vqakJGiC41fv376upqSEiWwkIgnDZ6StWrEB4Nhp6/fq1oqIiIlovCRbT5eTk4FMQc/Goq6szMzNbvnw5/iSHw6mpqcHm48MqGb5WCKx0QXCbmMKTevfunYaGBoFTYjiiLRLsb9sH3tQ3b97o6OiAePwHxzwGTzwUFRVnz54NE4oAzIyIi4vDVsDhl2FhjBkz5ty5cyhu/jfQ3d1tY2PD62gVT8DykLitwM3Dt3YJFA8ajYaFloLRfw8Pjz5bYTzu7u74qX7op+IB58GH7uzsjCCInJyciOKRkJCAzzNf8aDT6bDcoc9uOLStkydPxu+Nioq9eJSUlCgrK4NHEgNe70OHDsFbLUSP4TyZTObqW92/f59KpX558egvUKmePXs2YsQIiXighN5+Y2MjhUKxt7fHiwfaOyqGomhJSYmbmxvvVqFaWlobNmyoqKhAcZFysK+zWKwhJB537tyRiIednR1YigMXD6xJEkUzsBb5woULKM9UXQ0Njffv36O9Mdog5czMTARBsCXfwjE3N4d1CVie+YoHiqIxMTGiTP8F8Th79ixXGYm5eMD29FzrPGBpDpvNxta+CtFOGRmZ5ORkruasrq5OW1t77969ROVzkMQDbpNOp2NuK4l4EJUsWB5z5szhEg9sr3IURRkMRl5eXkRExA8/ODr6/vDDz+EhoZik93hMol44Bmi4tGPqbp8xQNMhLq6Oiwas6AhWWzmkpOTEwgDflZyYmIihUKBFf8wFgd1C+wjBBetE584nAENIJFIEJUTfzOC1oJ2dHS4urpCIlK94OcZYwfOzs68q3uSk5PV1NQaGhoGXPqDSltbm6WlZUBAAP4k9rrW19e7ubnxPhesYKWkpA4fPsyVJofDaW1tFTLbagAMkniAO76trc3Q0FAiHijRIdkpFEpgYCBXbrnGsQTBwcV1xufqvyMeHNxcXvwZFEUPHz48YsQICPMq+sAhNjSIlSc2HAV/16xZY2trS3hs0O+++27NmjWogEVUoooHNpoKtqogfwi0TSoqKnw3HN23b5+0tDRE6+S6z0uXLoGnHnzxeCsEH93vp59+wvxd2HchCg2X+wUuKC0tnTJlCtbRBmcORObA0ndxceG7RDk5OVldXR3sJDGEzWY7OjouW7ZM0AU9PT1JSUm8C7tkZGScnJyys7NRfnWipaVFS0tL/N1WAJ1Ol4jHYFgew4cPt7e3J3YC29ASj9u3bysrK/Nd5/E5pKSkaGhoED4zcN26debm5p9j0DQ2Nj59+rSkpKSkpKS0tLSkpKS4uHjixImWlpZc854wRB3zwIYu9u/fLzxKgZaW1vnz5/nmb9++fQiCHDlyBP10bgykXFNTM2PGDEHJ6uvrw8RzTm8YAOzru3fvlpWV5ZptBatAURTt7OzcsGEDX+8NlUr19/evra2Fy7hCsoOBKbZ7mLNYLHt7e0HigT3pioqKyMjIadOmubm5OTs7BwcHX7x4ERa79vT0MJlMrnosEY9BYsiJB+Y8IBBbW9uhIh63bt2i0WiFhYXYAK3osNns169fX7x48dKlS7CkH46vXLmyZs0aKpWalpaWm5srSkh2fET33NzclJSUqKio/fv3JyQk5OTkrF+/3tXVdfr06dra2giCTJgwYfr06a6urlNFw8XFxc3Nbdq0aU5OTsbGxlyDWNC9lpOTgw70AMUDZAdzidy8edPKyopvEz9r1izYZpJvVQbxSE5ORnnm8EE1bW5uPnjwoIWFBbbxBoIgZDJ55syZWLK80zqPHj06fPhwrthW2CJEFEW7u7sLCgq2bNliY2NDJpOVlJQ8PDxWrlx5/fp1yCeWJv7dPnbsmLS0dFpaWn+q3JdDuHiw2WyYrQD/4i1cANvMnMsEFC4eeKtZxHyKIh4DbviGlnhMmzaN2DQ5HI65uXlUVBThySooKAw4t/A20en09vZ2Oo6WlpaJEydyTfEQW27cuIEgiJ6e3tdffz2mn4wdO3bEiBF8W0h5eXkVFRVy/4HQlgoKCtLS0nJychCvwcDAwMbGZv78+T4+PosXL/by8pozZ87cuXPniMzcuXPnzp3r6enp7e294FO2b9++ZMmShIQEaGwHKB68tLS0JCcnh4SEmJqaamho6OrqLlmyJCMjQ/iIDYjH0aNHubKCOfXg39bW1vLy8r1794aHh/yyy997lt54MABXvHgS0dHR0VFRTUNwekAAAaZSURBVGVlJdcSf64D4LfffkMQJC4urs9k/xFYLJaDg4MQ8YCpCrxuUK775XoQzc3Nurq6+DEPTm+IGizMDmaJ8l13yvfniouLsZDsXIqFt2v7C4PBMDY2FnPxgFvz8/Ozt7cXfiWdTq+trf3w4QOdTm9oaGhsbHzz5k1NTQ1XiPU3b968evXq9evXL168MDMzc3Fxqaqq4r2GCwjJXlRUFBsbW1BQUFhYGBkZuX379qioqM2bN0dGRm7uJTg4GEEQHR2diIiIzX0RERERERHh5eUVEhISGRm5du3aiRMnTpgwQVtbW1tbW0tLS0dHR1tbW0NDA4LyBgYGiu2TwuBwONXV1Vu2bPnxxx/XDIh169aFhYWFhoZu2LAhJCQkNDQ0NDR006ZNV69effny5fPP4MWLF+Xl5eXl5dXV1fX19YSPc4jOAMUDAwICw/hPnwgSj8/kwYMHqqqqn7NXBF9APBITE4lNlii6urqEjHmA4TWAQu7o6NDX1wfXIj61Aeayl+fPnysqKsJAC4HU1NRg6zzEc4U5pt++vr4Igri7uy9evNiPH/7+/sbGxlJSUhQKxdjYWFNTU09PT15eXkFBgUwmKygowAHWDwVgIomCggKFQumz64rF4UcQRENDw8DAAJy3RkZGI0eOhJ0h9PX1DQwMxo8fb25ubmhoqN8XBgYGI0eONDExMTQ0NDAwMDQ0tLOz8/Pzs7GxWbhwYWxs7Jo1a8LDw2NjY3fv3r1nz55r1671iHf8Y7SfwQ7+swxcPGDvWOzfnp6ePsMR90s88D5E4VfeuXNHRUWFcPE4ceKEOIsHi8VydHRcsmSJkGuw8SEMVl+UlZWpqqpGRERgZyD6dFtb25MnTx49enTx4sXs7Oy8vLw7d+6kp6efOXPmbF9kZWVBIF4HB4esrKzMzEz8p+np6ZmZmVu2bJk+fbq7u7ubm5urqysM0ri7uzs6Ojrww9HRERy1CILEx8ejgre4/2fBVHzv3r0uLi52dna2trY2NjbW/HBwcABPtL29vZub27JlyzZu3Hjo0KGYmJhff/01KSkpLS3t9OnTp0+fPnXqVGpq6qlTpzIyMjIyMlJSUv7444/U1NTTgoHrU1NTz5w5c+rUqYKCgtbW1nPnzpWXl3d2djI/hcFgdHR0tLe3MxgMplAYDAa4p9p7gRE1JpMpqEzE80nhwfahIHCMiq/LfUjDXzzy8vJUVFSwFeZ9eroFLUHk4sCBAwhP/MHP5/Hjx6qqqhBMhUCOHz+OIAiM0oshXV1dTk5OysrKu3fv3rdv314eEhMTPT09x40bN3r06K+/trY2JhvRFs8xsbGsCwfQZCRI0di1xsbG+vr68NmG5j3Vk5ODjq8Cn1BJpMVFRWVlJSgswwdYfynFAoFm8Wnq6trZmZmYmKio6MjLy/v4eHx/fffewtgwYIFQUFBVVVVqBiHZMfHVRUxh2J7L/0Fc5djk02HxK1hIWwJzCqHZ/7uUIf/fh5/23mpoaV5Dzzwc2Gjp58iRWfGw2++XLl2/evGlsbKysrKyoqKjqJ9XV1TDbKiYmJi8vLy8v7/r165cuXdrSS2Rk5MaNG0P6w8aNGzds2GBoaCi2Yx4cDofBYPj7+2toaKgKRkVFRUNDY+nSpbNnzw4KCtogAmFhYVu3bt28eTPX+ZCQkE2bNm3atAn84+Hh4QkJCeB7raysfCkCr169qqqq4ntxZWUlPMrq6uqGhob29vaWlpYPHz5UV1f/0yUtQYIE/ggUDykpqS1btuzdu3fx4sWLFi3auXNnUFDQvn371q9f7+Xl5eXlJagzyBcvL68FCxaMGzcOQRBzc3NbW1svLy9fX19nZ2cSiTR8+HAjIyMZGZmBTUJAcIvgpKSkePeC19PT67PTzYu5ubm9vf29e/fEsKPE4XC6u7vb2tqwbSkF0d9Q5+IAvsD/Nd00CRL+ZfAXj7Kysq+++gq/zFtbW1tOTs7Dw8PV1dXe3t7BwcFeZLCL3dzcPD09wakNvmxHR0d3d/cZM2a4uLgsX748PT397Nmzf/aT7OzsnJycrKws8KH/+eefZ86cOXfuXE5Ozrlz5y5evEin08F3LzpdXV3g0kXFdRqP6K0qttwXs8Q/H3Dlw4gUUWlyesNlwpzpf5mDWIKEfxn8xzxQFK2oqLh7925RUVFxcXFpaemrV68eP378xbP3z8MRS+UABtA6E/vrKNHlw5VPcS58CRL+43CLhwQJEiRIkNAnEvGQIEGCBAn95v8BtRjE+y+OnugAAAAASUVORK5CYIIA) 

输入格式

一个整数n(n<=50)

输出格式

骨牌的铺法

3
4