Col 游戏是由 John Conway 描述的一种地图染色游戏，他将其归功于 Colin Vout。

游戏由两名玩家 Alice 和 Bob 进行。游戏在一个图上进行，玩家轮流对图的顶点进行染色，Alice 先手。每次移动时，玩家选择一个尚未染色的顶点并将其染成自己的颜色。Alice 将顶点染成红色，Bob 将顶点染成蓝色。限制条件是：玩家不能为与自己已染色顶点相邻的顶点染色。无法进行移动的玩家输掉游戏。

例如，在下图所示的图的局面中（红色顶点标记为 "R"，蓝色顶点标记为 "B"），Alice 可以通过为顶点 3 或顶点 5 染色来进行她的移动。如果她为顶点 3 染色，Bob 随后可以为顶点 2 染色。然后 Alice 为顶点 5 染色，Bob 没有可行的移动并输掉游戏。然而，如果双方在同一个图上都采取最优策略，无论 Alice 如何移动，Bob 都能获胜（请自行验证！）。

Alice 和 Bob 决定在竹林（bamboo forests）上玩这个游戏。竹林是一个具有 $k$ 个连通分量的图，其中第 $i$ 个连通分量是一条路径——即竹子（bamboo）。下图展示了一个由长度分别为 2、2 和 4 的竹子组成的竹林。

他们分别准备了 $n$ 根长度为 $a_1, a_2, \dots, a_n$ 的竹子，现在他们想从中选择 $k$ 根来构建一个图并进行游戏。Bob 认为无论如何他都会赢，因此他允许 Alice 选择 $k$ 根竹子来构建游戏所用的图。Alice 想知道，有多少种方法可以从给定的竹子中选择 $k$ 根，使得如果双方都采取最优策略，她能够赢得游戏。请帮助她求出答案，并将结果对 $242\,121\,643$ 取模。

输入格式

输入文件包含多组测试数据。

每组测试数据的第一行包含 $n$ 和 $k$（$1 \le k \le n \le 100$）。第二行包含 $n$ 个整数：$a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

最后一组测试数据之后紧跟一行，包含两个零，该行不应被处理。每个输入文件最多包含 1000 组测试数据。

输出格式

对于每组测试数据，输出一个整数：从给定的 $n$ 根竹子中选择 $k$ 根，使得 Alice 在生成的竹林上进行 Col 游戏时能够获胜的方法数。答案必须对 $242\,121\,643$ 取模。

样例

输入样例 1

5 3
1 1 3 4 5
4 2
2 2 2 2
0 0

输出样例 1

6
0