完美数列

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M ≤ m*p，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

时间限制：1000

内存限制：65536

输入

输入第一行给出两个正整数 n 和 p，其中 n（≤ 105）是输入的正整数的个数，p（≤ 109）是给定的参数。第二行给出 n 个正整数，每个数不超过 109。

输出

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

样例输入

10 8
2 3 20 4 5 1 6 7 8 9

样例输出

8

两枚硬币

伊娃喜欢收集全宇宙的硬币，包括火星币等等。一天她到了一家宇宙商店，这家商店可以接受任何星球的货币，但有一个条件，无论什么价格，都必须用 2 枚硬币一次付清，不能多也不能少。而她有多达 105 个硬币，于是求助于你。给定任一价格，请帮她找出可以付款的 2 枚硬币。

时间限制：1000

内存限制：65536

输入

第 1 行给出 2 个正整数：n (≤ 105)为硬币枚数、m（≤ 103）为伊娃要付清的价格； 第 2 行给出 n 枚硬币的面值，均为不超过 500 的正整数。同行数字间以空格分隔。

输出

在一行中输出两枚硬币的面值 v1 和 v2 ，以 1 个空格分隔，满足条件 v1+v2=m，并且 v1 ≤ v2。如果这样的解不唯一，输出 v1 最小的那个解。如果解不存在，则输出 `No Solution`。

样例输入

样例#1：

8 15
1 2 8 7 2 4 11 15

样例#2：

7 14
1 8 7 2 4 11 15

样例输出

样例#1：

4 11

样例#2：

No Solution

二进制串的评分

对于一个给定的二进制串 s（即仅由字符 0 和 1 组成的串），其评分是这样计算的：将原串切分为若干段，使得每段包含的字符是一样的，且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值（如果只有一段，评分就是这段的长度）。

异或（Exclusive OR，简称 XOR）是一种数学运算符，用于计算机中的位运算。当且仅当两个输入值不同时，异或运算输出为真（1），否则输出为假（0）。

例如，串 "10001100001" 可以切分为 5 段，即 "1"、"000"、"11"、"0000"、"1"，其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。

假设每一步我们可以交换 2 个相邻的字符，并且可以这样执行任意多步（当然也可以执行 0 步）。对每个可能的评分 x，你能得到多少个不同的串？将原串 s 通过交换操作变成评分为 x 的串，所用的最少步骤是多少次？

时间限制：1000

内存限制：65536

输入

输入在一行中给出非空的原始二进制串 s，其长度不超过 64。

输出

对每个可能的评分，在一行中输出 3 个空格分隔的整数，依次为：评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。

样例输入

010

样例输出

1 1 0
3 2 1

多样解码

将一个由大写英文字母组成的字符串加密为一个数字串，可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是，反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`，也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的，不能被解码为 `H`。

本题就请你计算一下，给定的数字串有多少种不同的解码结果。

时间限制：1000

内存限制：65536

输入

输入在一行中给出一个不超过 104 位的数字串，串非空且不包含空格。

输出

输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大，你只需要输出其对 1000000007 取模后的结果。

样例输入

1213407

样例输出

5