/// general import pub use std::{ cmp::{max, min, Ordering, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, convert::Infallible, convert::{TryFrom, TryInto}, fmt::{Debug, Display, Formatter}, io::{stdin, stdout, BufRead, BufWriter, Write}, iter::{Product, Sum}, marker::PhantomData, mem::swap, ops::{ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Bound, Deref, DerefMut, Div, DivAssign, Mul, MulAssign, Neg, Not, RangeBounds, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign, }, str::{from_utf8, FromStr}, }; /// min-max macros #[allow(unused_macros)] macro_rules! chmin {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_min = min!($($cmps),+);if $base > cmp_min {$base = cmp_min;true} else {false}}};} #[allow(unused_macros)] macro_rules! chmax {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_max = max!($($cmps),+);if $base < cmp_max {$base = cmp_max;true} else {false}}};} #[allow(unused_macros)] macro_rules! min {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{if $a > $b {$b} else {$a}}};($a:expr, $($rest:expr),+ $(,)*) => {{let b = min!($($rest),+);if $a > b {b} else {$a}}};} #[allow(unused_macros)] macro_rules! max {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{if $a > $b {$a} else {$b}}};($a:expr, $($rest:expr),+ $(,)*) => {{let b = max!($($rest),+);if $a > b {$a} else {b}}};} pub fn to_lr>(range: &R, length: usize) -> (usize, usize) { let l = match range.start_bound() { Bound::Unbounded => 0, Bound::Included(&s) => s, Bound::Excluded(&s) => s + 1, }; let r = match range.end_bound() { Bound::Unbounded => length, Bound::Included(&e) => e + 1, Bound::Excluded(&e) => e, }; assert!(l <= r && r <= length); (l, r) } /// stdin reader pub struct Reader { reader: R, buf: VecDeque, } impl Iterator for Reader { type Item = String; fn next(&mut self) -> Option { if self.buf.is_empty() { let mut buf = Vec::new(); self.reader.read_to_end(&mut buf).unwrap(); let s = from_utf8(&buf).expect("utf8でない文字列が入力されました."); s.split_whitespace() .map(ToString::to_string) .for_each(|s| self.buf.push_back(s)); } self.buf.pop_front() } } impl Reader { pub fn new(reader: R) -> Reader { Reader { reader, buf: VecDeque::new(), } } pub fn val(&mut self) -> T { self.next() .map(|token| token.parse().ok().expect("型変換エラー")) .expect("入力が足りません") } pub fn vec(&mut self, length: usize) -> Vec { (0..length).map(|_| self.val()).collect() } pub fn chars(&mut self) -> Vec { self.val::().chars().collect() } pub fn digits(&mut self) -> Vec { self.val::() .chars() .map(|c| (c as u8 - b'0') as i64) .collect() } pub fn char_map(&mut self, h: usize) -> Vec> { (0..h).map(|_| self.chars()).collect() } pub fn bool_map(&mut self, h: usize, ng: char) -> Vec> { self.char_map(h) .iter() .map(|v| v.iter().map(|&c| c != ng).collect()) .collect() } pub fn matrix(&mut self, h: usize, w: usize) -> Vec> { (0..h).map(|_| self.vec(w)).collect() } } /// stdin writer pub struct Writer { writer: BufWriter, } impl Writer { pub fn new(write: W) -> Self { Self { writer: BufWriter::new(write), } } pub fn println(&mut self, s: S) { writeln!(self.writer, "{}", s).expect("Failed to write.") } pub fn print(&mut self, s: S) { write!(self.writer, "{}", s).expect("Failed to write.") } pub fn print_join(&mut self, v: &[S], separator: &str) { v.iter().fold("", |sep, arg| { write!(self.writer, "{}{}", sep, arg).expect("Failed to write."); separator }); writeln!(self.writer).expect("Failed to write."); } } #[allow(dead_code)] fn main() { let stdin = stdin(); let stdout = stdout(); solve(Reader::new(stdin.lock()), Writer::new(stdout.lock())); } /// マグマ /// 二項演算: $`M \circ M \to M`$ pub trait Magma { /// マグマを構成する集合$`M`$ type M: Clone + PartialEq; /// マグマを構成する演算$`op`$ fn op(x: &Self::M, y: &Self::M) -> Self::M; } /// 結合則 /// $`\forall a,\forall b, \forall c \in T, (a \circ b) \circ c = a \circ (b \circ c)`$ pub trait Associative {} /// 単位的 pub trait Unital: Magma { /// 単位元 identity element: $`e`$ fn unit() -> Self::M; } /// 可換 pub trait Commutative: Magma {} /// 可逆的 /// $`\exists e \in T, \forall a \in T, \exists b,c \in T, b \circ a = a \circ c = e`$ pub trait Invertible: Magma { /// $`a`$ where $`a \circ x = e`$ fn inv(x: &Self::M) -> Self::M; } /// 冪等性 pub trait Idempotent: Magma {} /// 半群 /// 1. 結合則 pub trait SemiGroup: Magma + Associative {} impl SemiGroup for M {} /// モノイド /// 1. 結合則 /// 1. 単位元 pub trait Monoid: Magma + Associative + Unital { /// $`x^n = x\circ\cdots\circ x`$ fn pow(&self, x: Self::M, mut n: usize) -> Self::M { let mut res = Self::unit(); let mut base = x; while n > 0 { if n & 1 == 1 { res = Self::op(&res, &base); } base = Self::op(&base, &base); n >>= 1; } res } } impl Monoid for M {} /// 可換モノイド pub trait CommutativeMonoid: Magma + Associative + Unital + Commutative {} impl CommutativeMonoid for M {} /// 群 /// 1. 結合法則 /// 1. 単位元 /// 1. 逆元 pub trait Group: Magma + Associative + Unital + Invertible {} impl Group for M {} /// アーベル群 pub trait AbelianGroup: Magma + Associative + Unital + Commutative + Invertible {} impl AbelianGroup for M {} /// Band /// 1. 結合法則 /// 1. 冪等律 pub trait Band: Magma + Associative + Idempotent {} impl Band for M {} /// 作用付きモノイド pub trait MapMonoid { /// モノイドM type Mono: Monoid; type Func: Monoid; /// 値xと値yを併合する fn op( &self, x: &::M, y: &::M, ) -> ::M { Self::Mono::op(x, y) } fn unit() -> ::M { Self::Mono::unit() } /// 作用fをvalueに作用させる fn apply( &self, f: &::M, value: &::M, ) -> ::M; /// 作用fの単位元 fn identity_map() -> ::M { Self::Func::unit() } /// composition: /// $`h() = f(g())`$ fn compose( &self, f: &::M, g: &::M, ) -> ::M { Self::Func::op(f, g) } } /// 加算の単位元 pub trait Zero { fn zero() -> Self; } /// 乗算の単位元 pub trait One { fn one() -> Self; } /// 下に有界 pub trait BoundedBelow { fn min_value() -> Self; } /// 上に有界 pub trait BoundedAbove { fn max_value() -> Self; } /// 整数 #[rustfmt::skip] pub trait Integral: 'static + Send + Sync + Copy + Ord + Display + Debug + Add + Sub + Mul + Div + Rem + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + Sum + Product + BitOr + BitAnd + BitXor + Not + Shl + Shr + BitOrAssign + BitAndAssign + BitXorAssign + ShlAssign + ShrAssign + Zero + One + BoundedBelow + BoundedAbove{} macro_rules! impl_integral { ($($ty:ty),*) => { $( impl Zero for $ty { fn zero() -> Self { 0 }} impl One for $ty { fn one() -> Self { 1 }} impl BoundedBelow for $ty { fn min_value() -> Self { Self::min_value() }} impl BoundedAbove for $ty { fn max_value() -> Self { Self::max_value() }} impl Integral for $ty {} )* }; } impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize); pub struct Gcd(Infallible, PhantomData S>); impl Magma for Gcd { type M = S; fn op(x: &S, y: &S) -> S { let (mut x, mut y) = (x.clone(), y.clone()); if y > x { swap(&mut x, &mut y); } while y != S::zero() { x %= y.clone(); swap(&mut x, &mut y); } x } } pub fn mi(i: i64) -> Mi { Mi::new(i) } pub trait Mod: Copy + Clone + Debug { fn get() -> i64; } pub type Mi = ModInt; #[derive(Copy, Clone, Eq, PartialEq, Debug)] pub struct Mod1e9p7; #[derive(Copy, Clone, Eq, PartialEq, Debug)] pub struct Mod1e9p9; #[derive(Copy, Clone, Eq, PartialEq, Debug)] pub struct Mod998244353; impl Mod for Mod1e9p7 { fn get() -> i64 { 1_000_000_007 } } impl Mod for Mod1e9p9 { fn get() -> i64 { 1_000_000_009 } } impl Mod for Mod998244353 { fn get() -> i64 { 998_244_353 } } #[derive(Copy, Clone, Eq, PartialEq)] pub struct ModInt { n: i64, _p: PhantomData M>, } impl ModInt { pub fn new(n: i64) -> Self { Self { n: n.rem_euclid(M::get()), _p: PhantomData, } } pub fn pow(mut self, mut e: i64) -> ModInt { let mut result = Self::new(1); while e > 0 { if e & 1 == 1 { result *= self.n; } e >>= 1; self *= self.n; } result } pub fn get(self) -> i64 { self.n } } impl Add for ModInt { type Output = Self; fn add(self, rhs: i64) -> Self { self + ModInt::new(rhs.rem_euclid(M::get())) } } impl Add> for ModInt { type Output = Self; fn add(self, rhs: Self) -> Self { let mut n = self.n + rhs.n; if n >= M::get() { n -= M::get(); } Self { n, _p: self._p } } } impl AddAssign for ModInt { fn add_assign(&mut self, rhs: i64) { *self = *self + rhs } } impl AddAssign> for ModInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs } } impl Neg for ModInt { type Output = Self; fn neg(self) -> Self { Self::new(-self.n) } } impl Sub for ModInt { type Output = Self; fn sub(self, rhs: i64) -> Self { self - ModInt::new(rhs.rem_euclid(M::get())) } } impl Sub> for ModInt { type Output = Self; fn sub(self, rhs: Self) -> Self { let mut n = self.n - rhs.n; if n < 0 { n += M::get(); } Self { n, _p: self._p } } } impl SubAssign for ModInt { fn sub_assign(&mut self, rhs: i64) { *self = *self - rhs } } impl SubAssign> for ModInt { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs } } impl Mul for ModInt { type Output = Self; fn mul(self, rhs: i64) -> Self { ModInt::new(self.n * (rhs % M::get())) } } impl Mul> for ModInt { type Output = Self; fn mul(self, rhs: Self) -> Self { self * rhs.n } } impl MulAssign for ModInt { fn mul_assign(&mut self, rhs: i64) { *self = *self * rhs } } impl MulAssign> for ModInt { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs } } impl Div for ModInt { type Output = Self; fn div(self, rhs: i64) -> Self { self * ModInt::new(rhs).pow(M::get() - 2) } } impl Div> for ModInt { type Output = Self; fn div(self, rhs: Self) -> Self { self / rhs.n } } impl DivAssign for ModInt { fn div_assign(&mut self, rhs: i64) { *self = *self / rhs } } impl DivAssign> for ModInt { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs } } impl Display for ModInt { fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { write!(f, "{}", self.n) } } impl Debug for ModInt { fn fmt(&self, f: &mut Formatter) -> std::fmt::Result { write!(f, "{}", self.n) } } impl Deref for ModInt { type Target = i64; fn deref(&self) -> &Self::Target { &self.n } } impl DerefMut for ModInt { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.n } } impl Sum for ModInt { fn sum>(iter: I) -> Self { iter.fold(Self::new(0), |x, a| x + a) } } impl From for ModInt { fn from(i: i64) -> Self { Self::new(i) } } impl From> for i64 { fn from(m: ModInt) -> Self { m.n } } impl Zero for ModInt { fn zero() -> Self { Self::new(0) } } impl Associative for Gcd {} impl Unital for Gcd { fn unit() -> S { S::zero() } } impl Commutative for Gcd {} impl Idempotent for Gcd {} pub fn solve(mut reader: Reader, mut writer: Writer) { let (n, k) = (reader.val::(), reader.val::()); let mut a = reader.vec::(n); a.iter_mut().for_each(|ai| *ai = Gcd::op(&ai, &k)); let mut map = HashMap::new(); map.insert(1, mi(1)); for ai in a { let mut tmp = HashMap::new(); for (&t, counts) in &map { *tmp.entry(Gcd::op(&k, &(t * ai))).or_insert(mi(0)) += *counts; } for (t, counts) in tmp { *map.entry(t).or_insert(mi(0)) += counts; } } writer.println(map.get(&k).unwrap_or(&mi(0))); }