use std::io::*;
use std::str::FromStr;
use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::VecDeque;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

const MOD: i64 = 1e+9 as i64 + 7;
fn count_best_bits(lower: i64, upper: i64) -> i64 {
    if lower == 0 {
        return 0;
    }
    let lower = lower - 1;
    let same = lower & upper;
    let diff = lower ^ upper;
    let lower_mask = (1i64 << (64 - diff.leading_zeros())) - 1;
    let upper_mask = !lower_mask;
    (same & upper_mask).count_ones() as i64 + 1
}
struct Solver {
    n: usize,
    k: i64,
    aseq: Vec<i64>,
    ans_range: HashMap<Vec<i64>, Vec<(i64, i64)>>,
}

impl Solver {
    fn new() -> Solver {
        let n: usize = read();
        let k: i64 = read();
        let mut aseq = vec![0; n];
        for i in 0..n {
            aseq[i] = read();
        }
        aseq.sort();
        Solver {
            n: n,
            k: k,
            aseq: aseq,
            ans_range: HashMap::new(),
        }
    }
    fn bfs(&self, cnt: i64, seq: &Vec<i64>, visited: &mut HashSet<Vec<i64>>) {
        let mut que = VecDeque::<(i64, Vec<i64>)>::new();
        que.push_back((cnt, seq.clone()));
        while let Some((cnt, seq)) = que.pop_front() {
            // println!("{:?}", seq);
            if visited.contains(&seq) {
                continue;
            }
            visited.insert(seq.clone());
            if cnt == 0 {
                continue;
            }
            let mut next1 = seq.clone();
            let mut next2 = seq.clone();
            for i in 0..self.n {
                next1[i] -= 1;
                next2[i] /= 2;
            }
            if seq[0] != 0 {
                que.push_back((cnt - 1, next1));
            }
            que.push_back((cnt - 1, next2));
        }
    }
    fn naive(&self) -> i64 {
        let mut visited = HashSet::new();
        self.bfs(self.k, &self.aseq, &mut visited);
        // println!("{:?}", visited);
        visited.len() as i64
    }
    fn make_offset_seq(&self, pow: i64, target_rest: i64) -> Vec<i64> {
        let mut ret = vec![0; self.n];
        for i in 0..self.n {
            ret[i] = self.aseq[i] / pow - (if self.aseq[i] % pow < target_rest {
                1
            } else {
                0
            });
        }
        let min_value = ret[0];
        for i in 0..self.n {
            ret[i] -= min_value;
        }
        ret
    }
    fn calc(&mut self, base: i64) {
        let pow = 1i64 << base;
        let mut rests = vec![0; self.n];
        for i in 0..self.n {
            rests[i] = self.aseq[i] % pow;
        }
        rests.sort();
        rests.dedup();
        // println!("rest: {:?}", rests);
        let mut prev = -1;
        for &rest in rests.iter() {
            let usea = count_best_bits(prev + 1, rest);
            let offset = if self.aseq[0] % pow < rest { 1 } else { 0 };
            let upper = self.aseq[0] / pow - offset;
            let cnt = std::cmp::min(self.k - (usea + base), upper);
            // println!("{} {} {}", usea, base, cnt);
            if cnt >= 0 {
                let range = (upper - cnt, upper);
                let offset_seq = self.make_offset_seq(pow, rest);
                // println!("{:?} {:?}", offset_seq, range);
                self.ans_range
                    .entry(offset_seq)
                    .or_insert(vec![])
                    .push(range);
            }
            prev = rest;
        }
    }
    fn solve(&mut self) -> i64 {
        for i in 0..62 {
            self.calc(i);
        }
        // println!("{:?}", self.ans_range);
        let mut ans: i64 = 0;
        for ranges in self.ans_range.values_mut() {
            ranges.sort();
            let mut prev = ranges[0];
            for &range in ranges.iter() {
                if range.0 <= prev.1 {
                    prev.1 = std::cmp::max(prev.1, range.1);
                } else {
                    ans = (ans + (prev.1 - prev.0 + 1)) % MOD;
                    prev = range;
                }
            }
            ans = (ans + (prev.1 - prev.0 + 1)) % MOD;
        }
        ans
    }
}

fn main() {
    let mut solver = Solver::new();
    let ans = solver.solve();
    println!("{}", ans);
    // let ans2 = solver.naive();
    // println!("{}", ans2);
    // assert!(ans == ans2);
}


Measured memory_bytes: 22780