小美的元素删除
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小美有一个数组,她希望删除k个元素,使得剩余的元素两两之间互为倍数关系。你能告诉小美有多少种删除方案吗?

由于答案过大,请对10^9+7取模。

输入描述:

第一行输入两个整数 n,k(1 \leq k\leq n \leq 10^3) 表示数组长度,删除的元素数量。

第二行输入 n 个整数表示数组 a(1 \leq a_i \leq 10^9)

保证给定的数组中不存在两个相等元素。

输出描述:

输出一个整数表示答案。
示例1

输入

复制
6 4
1 4 2 3 6 7

输出

复制
8

说明

方案1:删除1,4,2,7。
方案2:删除1,4,3,7。
方案3:删除1,3,6,7。
方案4:删除4,2,3,6。
方案5:删除4,2,3,7。
方案6:删除4,2,6,7。
方案7:删除4,3,6,7。
方案8:删除2,3,6,7。