{"raw_statement":[{"iden":"problem statement","content":"There are $N$ non-negative integers written on the blackboard: $A_1, ..., A_N$.\nSnuke can perform the following two operations at most $K$ times in total in any order:\n\n*   Operation A: Replace each integer $X$ on the blackboard with $X$ divided by $2$, rounded down to the nearest integer.\n*   Operation B: Replace each integer $X$ on the blackboard with $X$ minus $1$. This operation cannot be performed if one or more $0$s are written on the blackboard.\n\nFind the number of the different possible combinations of integers written on the blackboard after Snuke performs the operations, modulo $1,000,000,007$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 200$\n*   $1 \\leq A_i \\leq 10^{18}$\n*   $1 \\leq K \\leq 10^{18}$\n*   $A_i$ and $K$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $...$ $A_N$"},{"iden":"sample input 1","content":"2 2\n5 7"},{"iden":"sample output 1","content":"6\n\nThere are six possible combinations of integers on the blackboard: $(1, 1)$, $(1, 2)$, $(2, 3)$, $(3, 5)$, $(4, 6)$ and $(5, 7)$. For example, $(1, 2)$ can be obtained by performing Operation A and Operation B in this order."},{"iden":"sample input 2","content":"3 4\n10 13 22"},{"iden":"sample output 2","content":"20"},{"iden":"sample input 3","content":"1 100\n10"},{"iden":"sample output 3","content":"11"},{"iden":"sample input 4","content":"10 123456789012345678\n228344079825412349 478465001534875275 398048921164061989 329102208281783917 779698519704384319 617456682030809556 561259383338846380 254083246422083141 458181156833851984 502254767369499613"},{"iden":"sample output 4","content":"164286011"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}