\(\lfloor N/M \rfloor\) を \(10007\) で割った余りを求めるために必要な情報はなんでしょうか？

\(N\) を \(M \times 10007\) で割った余りが分かっていれば十分です。この値を \(r\) として、答えは \(\lfloor r/M \rfloor\) となります。
なお、制約より \(M \times 10007 \le 10^9\) なので、 \({\rm mod}\ (M \times 10007)\) を求めるにあたって \(64\)bit 符号付き整数型程度の桁数の整数型を使えば安全であることも分かります。

ここで、 \(1\) を \(k\) 個並べた レピュニット を \(R_k\) と書きます。例えば、 \(R_5=11111\) です。

求めるべきは次を \(M \times 10007\) で割った余りです。

• \(\displaystyle \sum_{i=1}^{N} c_i \times R_{l_i} \times 10^{\sum_{j=i+1}^{N} l_j}\)

レピュニット以外の部分に関しては容易で、問題はレピュニットです。
レピュニットを \({\rm mod}\ X\) 上で求める方法として \(R_k = \displaystyle \frac{10^{k}-1}{9}\) を利用する方法もあります(頻出です)が、今回は \({\rm mod}\ (M \times 10007)\) で \(9\) の逆元が取れない場合があるためこの方法は使えません。どうすればよいでしょうか？

今回は、 ダブリング と呼ばれる手法を用います。
ダブリングとは、以下の手法です。

• サイズ \(2^k\) について問題を解いた結果から、サイズ \(2^{k+1}\) について問題を解いた結果を得る行為を、十分大きな \(k\) に到達するまで繰り返す。
• サイズ \(n\) について問題を解いた結果を得たい場合、 \(n = 2^a+2^b+2^c+\dots\) と (二進表記を利用するなどして) 分解した上で、2べきのサイズについて問題を解いた結果を組み合わせてサイズ \(n\) について問題を解いた結果を得る。

詳しくは、以下の記事も参考にしてください。他にも、インターネット上に参考となる記事がたくさんあります。

• ダブリングの基本概念とその応用
• 【競技プログラミング】ダブリングまとめ
• AtCoderダブリング問題総まとめ（中３女子しらべ）
• [競プロ用]ダブリングまとめ

今回は、以下の要領でダブリングを適用可能です。

• \(R_1 = 1\) から始める。
• \(1 \le k < 30\) について \(R_{2^k} = R_{2^{k-1}} \times 10^{2^{k-1}} + R_{2^{k-1}}\) と得る。
• \(R_{2^k}\) を組み合わせて \(R_n\) を得る際に、 \(R_s\) が既知だとすると \(R_{s+2^k} = R_s \times 10^{2^k} + R_{2^k}\) と得ることができる。

こうすると、 \({\rm mod}\ (M \times 10007)\) 上での逆元計算をすることなくレピュニットを \(M \times 10007\) で割った余りを求めることができます。
あとは、先ほど示した値を求めることでこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll mod;

ll power(ll a,ll b){ // a^b
  ll res=1,cur=a;
  while(b>0){
    if(b&1ll){
      res*=cur; res%=mod;
    }
    cur*=cur; cur%=mod;
    b>>=1;
  }
  return res;
}

int main(){
  ll k,m;
  cin >> k >> m;
  mod=(m*10007);
  vector<ll> c(k),l(k);
  for(ll i=0;i<k;i++){
    cin >> c[i] >> l[i];
  }

  vector<ll> pow_keep(30); // 10^{2^d}
  pow_keep[0]=10;
  for(ll d=1;d<30;d++){
    pow_keep[d]=(pow_keep[d-1]*pow_keep[d-1])%mod;
  }

  vector<ll> Rpow2(30);
  Rpow2[0]=1;
  for(ll d=1;d<30;d++){
    Rpow2[d]=(Rpow2[d-1]*pow_keep[d-1]+Rpow2[d-1])%mod;
  }

  ll res=0;
  ll dgt=0;
  for(ll i=k-1;i>=0;i--){
    ll ce=(c[i]*power(10,dgt))%mod;
    ll R=0;
    for(ll d=29;d>=0;d--){
      if(l[i]&(1ll<<d)){
        R=(R*pow_keep[d]+Rpow2[d])%mod;
      }
    }
    res+=ce*R; res%=mod;
    dgt+=l[i];
  }
  cout << res/m << "\n";
  return 0;
}