I never said “640K should be enough for anybody! ”. —— Bill Gates
阿米巴是小强的好朋友。他经常和小强通过即时通讯工具聊天。但是，小强还是喜欢和阿米巴面对面的在一起的感觉，于是他想说服阿米巴放弃即时通讯工具。小强提出的一个理由是，别人可能偷看到他们两个人之间的相互说的“那些话”从而造出“大新闻”。
阿米巴认为他们可以通过加密聊天来解决这个问题。小强和阿米巴都知道，只有一次一密这种真正安全的加密算法才能保护住他们的信息。这种加密方法虽然很安全，但是需要在事前约定很长的一个随机串。
于是，小强又提出，他的 u 盘太小，根本存不下太多东西，一次无法从阿米巴那里拷贝足够长的随机串。为了减少事前约定的串的长度，阿米巴提出了一个“随机倍增器”。这个“随机倍增器”可以将一个 位的随机串变成一个 位的看起来也很随机的串。
具体的，对于一个长度为 的 串，选取参数 ，，阿米巴用下面的方法把它变成一个长度为 的串：
首先，令 为 ，。
对于每个 从 到 ，设输入的第 位是 ，做下面几个事情：
；
；
；
。
输出 的二进制位从低到高的第 位、第 位（例如，如果 （二进制是 ），，那么就是 和 ）。
在这里， 表示取模，即， 为一个 之间的整数，表示 模 的余数。表示从一次 位的循环左移，即，将 的所有二进制位向更高位移动一位，原来的第 位移动回第 位（比如，，因为 的二进制是 ，循环左移变成 ，就是 ）。
小强从这个算法的常数中一下就看出了这个算法改造自著名的 murmurHash3。不过，小强认为阿米巴连 NOIP 都没有考过，他改造出来的算法一定是有缺陷的。阿米巴偏偏不信这点。
为了向阿米巴说明这个算法的“随机性”不是特别强，小强想精心构造一个输入串，使得输出串中 的个数特别多。我们知道，如果这个算法真的很随机，因为输入只有 位，所以输出中应该是不会有太多的 的。曾经获得过 NOIP 普及组二等奖的小强还是有一定的算法能力的，他很快就想出了一个构造的算法。但是，问题在于小强没有带笔记本，他只能用自己的手机上的浏览器运行 javascript 来进行计算。但是手机上的内存非常紧张，需要用的数组根本存不下！
为了小强和阿米巴在一起的美好时光，你要利用非常紧缺的内存来完成输入串的构造。
