[ABC349] F - Subsequence LCM

F - Subsequence LCM

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 525 分

题面

给定一个长度为的正整数序列和一个正整数。求出的非空子序列中，元素的最小公倍数（LCM）为的子序列个数，取模。如果两个子序列的元素相同但位置不同，则视为不同的子序列。此外，单个元素的序列的LCM为该元素本身。

限制条件

• 所有输入值均为整数。

---

输入

输入从标准输入给出，格式如下：

输出

输出答案。

---

输入样例 1

4 6
2 3 4 6

输出样例 1

5

的元素LCM为的子序列有；共有五个。

---

输入样例 2

5 349
1 1 1 1 349

输出样例 2

16

即使一些子序列与另一些子序列相同，但如果它们来源于不同位置，则被视为不同。

---

输入样例 3

16 720720
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

输出样例 3

2688