UVA1489 Math teacher's homework

给出两个整数$K$，$n$ 和一个整数序列$M_1,M_2,M_3....M_n$， 求满足$X_1 \otimes X2 \otimes X3...\otimes Xn=K$ 且$0\leq X_i\leq M_i(i=1..n)$的解的个数。

每个测试点包含多组测试数据，但不超过$100$ 组。 每组测试数据的第一行包含两个整数$n$，$K$。 第二行包含n 个整数：$M_1,M_2,M_3...M_n$。 当$n=0$ 且$K=0$ 时读入结束。

于每组数据，输出一个数$ans$，表示符合条件的解的个数。由于答案可能会很 大，你只需要输出答案除以$10^9+3$ 的余数。 ## 输入样例 ``` 11 2047 1024 512 256 128 64 32 16 8 4 2 1 10 2047 1024 512 256 128 64 32 16 8 4 2 0 0 ``` ## 输出样例 ``` 1 0 ```