結果

問題 No.315 世界のなんとか3.5
ユーザー hashiryohashiryo
提出日時 2023-04-10 14:58:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,467 ms / 2,000 ms
コード長 24,952 bytes
コンパイル時間 8,011 ms
コンパイル使用メモリ 339,084 KB
実行使用メモリ 132,476 KB
最終ジャッジ日時 2024-04-15 19:53:39
合計ジャッジ時間 22,425 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 243 ms
23,152 KB
testcase_13 AC 232 ms
23,024 KB
testcase_14 AC 466 ms
39,320 KB
testcase_15 AC 461 ms
39,068 KB
testcase_16 AC 461 ms
39,320 KB
testcase_17 AC 454 ms
39,196 KB
testcase_18 AC 234 ms
23,192 KB
testcase_19 AC 234 ms
23,188 KB
testcase_20 AC 235 ms
23,056 KB
testcase_21 AC 232 ms
23,184 KB
testcase_22 AC 466 ms
39,068 KB
testcase_23 AC 457 ms
39,192 KB
testcase_24 AC 459 ms
39,064 KB
testcase_25 AC 468 ms
39,196 KB
testcase_26 AC 458 ms
35,356 KB
testcase_27 AC 475 ms
39,196 KB
testcase_28 AC 631 ms
68,140 KB
testcase_29 AC 1,032 ms
108,780 KB
testcase_30 AC 1,040 ms
108,904 KB
testcase_31 AC 1,037 ms
108,864 KB
testcase_32 AC 944 ms
68,676 KB
testcase_33 AC 490 ms
50,384 KB
testcase_34 AC 1,300 ms
132,476 KB
testcase_35 AC 1,467 ms
132,476 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on

#include <type_traits>
#include <cassert>
template <class Int> constexpr inline Int mod_inv(Int a, Int mod) {
 static_assert(std::is_signed_v<Int>);
 Int x= 1, y= 0, b= mod;
 for (Int q= 0, z= 0, c= 0; b;) z= x, c= a, x= y, y= z - y * (q= a / b), a= b, b= c - b * q;
 return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;
}
namespace math_internal {
using namespace std;
using u8= uint8_t;
using u32= uint32_t;
using u64= uint64_t;
using i64= int64_t;
using u128= __uint128_t;
#define CE constexpr
#define IL inline
#define NORM \
 if (n >= mod) n-= mod; \
 return n
#define PLUS(U, M) \
 CE IL U plus(U l, U r) const { \
  if (l+= r; l >= M) l-= M; \
  return l; \
 }
#define DIFF(U, C, M) \
 CE IL U diff(U l, U r) const { \
  if (l-= r; l >> C) l+= M; \
  return l; \
 }
#define SGN(U) \
 static CE IL U set(U n) { return n; } \
 static CE IL U get(U n) { return n; } \
 static CE IL U norm(U n) { return n; }
template <class u_t, class du_t, u8 B, u8 A> struct MP_Mo {
 u_t mod;
 CE MP_Mo(): mod(0), iv(0), r2(0) {}
 CE MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {}
 CE IL u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); }
 PLUS(u_t, mod << 1)
 DIFF(u_t, A, mod << 1)
 CE IL u_t set(u_t n) const { return mul(n, r2); }
 CE IL u_t get(u_t n) const {
  n= reduce(n);
  NORM;
 }
 CE IL u_t norm(u_t n) const { NORM; }
private:
 u_t iv, r2;
 static CE u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; }
 CE IL u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); }
};
struct MP_Na {
 u32 mod;
 CE MP_Na(): mod(0){};
 CE MP_Na(u32 m): mod(m) {}
 CE IL u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32)
};
struct MP_Br {  // mod < 2^31
 u32 mod;
 CE MP_Br(): mod(0), s(0), x(0) {}
 CE MP_Br(u32 m): mod(m), s(31 - __builtin_clz(m - 1) + 64), x(((u128(1) << s) + m - 1) / m) {}
 CE IL u32 mul(u32 l, u32 r) const { return rem(u64(l) * r); }
 PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) private: u8 s;
 u64 x;
 CE IL u64 quo(u64 n) const { return (u128(x) * n) >> s; }
 CE IL u32 rem(u64 n) const { return n - quo(n) * mod; }
};
struct MP_Br2 {  // 2^20 < mod <= 2^41
 u64 mod;
 CE MP_Br2(): mod(0), x(0) {}
 CE MP_Br2(u64 m): mod(m), x((u128(1) << 84) / m) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); }
 PLUS(u64, mod << 1)
 DIFF(u64, 63, mod << 1)
 static CE IL u64 set(u64 n) { return n; }
 CE IL u64 get(u64 n) const { NORM; }
 CE IL u64 norm(u64 n) const { NORM; }
private:
 u64 x;
 CE IL u128 quo(const u128 &n) const { return (n * x) >> 84; }
 CE IL u64 rem(const u128 &n) const { return n - quo(n) * mod; }
};
struct MP_D2B1 {
 u8 s;
 u64 mod, d, v;
 CE MP_D2B1(): s(0), mod(0), d(0), v(0) {}
 CE MP_D2B1(u64 m): s(__builtin_clzll(m)), mod(m), d(m << s), v(u128(-1) / d) {}
 CE IL u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; }
 PLUS(u64, mod) DIFF(u64, 63, mod) SGN(u64) private: CE IL u64 rem(const u128 &u) const {
  u128 q= (u >> 64) * v + u;
  u64 r= u64(u) - (q >> 64) * d - d;
  if (r > u64(q)) r+= d;
  if (r >= d) r-= d;
  return r;
 }
};
template <class u_t, class MP> CE u_t pow(u_t x, u64 k, const MP &md) {
 for (u_t ret= md.set(1);; x= md.mul(x, x))
  if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret;
}
#undef NORM
#undef PLUS
#undef DIFF
#undef SGN
#undef CE
}
namespace math_internal {
#define CE constexpr
struct m_b {};
struct s_b: m_b {};
template <class mod_t> CE bool is_modint_v= is_base_of_v<m_b, mod_t>;
template <class mod_t> CE bool is_staticmodint_v= is_base_of_v<s_b, mod_t>;
template <class MP, u64 MOD> struct SB: s_b {
protected:
 static CE MP md= MP(MOD);
};
template <class Int, class U, class B> struct MInt: public B {
 using Uint= U;
 static CE inline auto mod() { return B::md.mod; }
 CE MInt(): x(0) {}
 CE MInt(const MInt &r): x(r.x) {}
 template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr> CE MInt(T v): x(B::md.set(v.val() % B::md.mod)) {}
 template <class T, enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr> CE MInt(T n): x(B::md.set((n < 0 ? ((n= (-n) % B::md.mod) ? B::md.mod - n : n) : n % B::md.mod))) {}
 CE MInt operator-() const { return MInt() - *this; }
#define FUNC(name, op) \
 CE MInt name const { \
  MInt ret; \
  ret.x= op; \
  return ret; \
 }
 FUNC(operator+(const MInt &r), B::md.plus(x, r.x))
 FUNC(operator-(const MInt &r), B::md.diff(x, r.x))
 FUNC(operator*(const MInt &r), B::md.mul(x, r.x))
 FUNC(pow(u64 k), math_internal::pow(x, k, B::md))
#undef FUNC
 CE MInt operator/(const MInt &r) const { return *this * r.inv(); }
 CE MInt &operator+=(const MInt &r) { return *this= *this + r; }
 CE MInt &operator-=(const MInt &r) { return *this= *this - r; }
 CE MInt &operator*=(const MInt &r) { return *this= *this * r; }
 CE MInt &operator/=(const MInt &r) { return *this= *this / r; }
 CE bool operator==(const MInt &r) const { return B::md.norm(x) == B::md.norm(r.x); }
 CE bool operator!=(const MInt &r) const { return !(*this == r); }
 CE bool operator<(const MInt &r) const { return B::md.norm(x) < B::md.norm(r.x); }
 CE inline MInt inv() const { return mod_inv<Int>(val(), B::md.mod); }
 CE inline Uint val() const { return B::md.get(x); }
 friend ostream &operator<<(ostream &os, const MInt &r) { return os << r.val(); }
 friend istream &operator>>(istream &is, MInt &r) {
  i64 v;
  return is >> v, r= MInt(v), is;
 }
private:
 Uint x;
};
template <u64 MOD> using ModInt= conditional_t < (MOD < (1 << 30)) & MOD, MInt<int, u32, SB<MP_Mo<u32, u64, 32, 31>, MOD>>, conditional_t < (MOD < (1ull << 62)) & MOD, MInt<i64, u64, SB<MP_Mo<u64, u128, 64, 63>, MOD>>, conditional_t<MOD<(1u << 31), MInt<int, u32, SB<MP_Na, MOD>>, conditional_t<MOD<(1ull << 32), MInt<i64, u32, SB<MP_Na, MOD>>, conditional_t<MOD <= (1ull << 41), MInt<i64, u64, SB<MP_Br2, MOD>>, MInt<i64, u64, SB<MP_D2B1, MOD>>>>>>>;
#undef CE
}
using math_internal::ModInt, math_internal::is_modint_v, math_internal::is_staticmodint_v;
template <class mod_t, size_t LM> mod_t get_inv(int n) {
 static_assert(is_modint_v<mod_t>);
 static const auto m= mod_t::mod();
 static mod_t dat[LM];
 static int l= 1;
 if (l == 1) dat[l++]= 1;
 while (l <= n) dat[l++]= dat[m % l] * (m - m / l);
 return dat[n];
}
template <class symbol_t> class Automaton {
 std::vector<int> table;
 std::vector<int8_t> info;
 std::vector<symbol_t> alph;
 const int m;
 template <class state_t, class F, class G, class H, std::enable_if_t<!std::is_integral_v<state_t>, std::nullptr_t> = nullptr> void build(const state_t &initial_state, const F &transition, const G &is_accept, const H &abs_reject) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<bool, std::invoke_result_t<H, state_t>>);
  std::map<state_t, int> encode;
  std::vector<state_t> decode;
  int ts= 0;
  decode.push_back(initial_state), encode.emplace(initial_state, ts++);
  for (int i= 0, k= 0; i < ts; ++i) {
   auto s= decode[i];
   table.resize(table.size() + m);
   for (int j= 0; j < m; ++j) {
    if (auto t= transition(s, j); abs_reject(t)) table[k++]= -1;
    else if (auto it= encode.find(t); it != encode.end()) table[k++]= it->second;
    else table[k++]= ts, decode.push_back(t), encode.emplace(t, ts++);
   }
  }
  info.resize(ts);
  for (int i= ts; i--;) info[i]= is_accept(decode[i]);
 }
 template <class state_t, class F, class G, class H, std::enable_if_t<std::is_integral_v<state_t>, std::nullptr_t> = nullptr> void build(const state_t &initial_state, const F &transition, const G &is_accept, const H &abs_reject) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<bool, std::invoke_result_t<H, state_t>>);
  std::unordered_map<state_t, int> encode;
  std::vector<state_t> decode;
  int ts= 0;
  decode.push_back(initial_state), encode.emplace(initial_state, ts++);
  for (int i= 0, k= 0; i < ts; ++i) {
   auto s= decode[i];
   table.resize(table.size() + m);
   for (int j= 0; j < m; ++j) {
    if (auto t= transition(s, j); abs_reject(t)) table[k++]= -1;
    else if (auto it= encode.find(t); it != encode.end()) table[k++]= it->second;
    else table[k++]= ts, decode.push_back(t), encode.emplace(t, ts++);
   }
  }
  info.resize(ts);
  for (int i= ts; i--;) info[i]= is_accept(decode[i]);
 }
 Automaton(const std::vector<symbol_t> &alphabet): alph(alphabet), m(alph.size()) {}
public:
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  build(initial_state, tr, is_accept, [](const state_t &) { return false; });
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const state_t &abs_rej_state): alph(alphabet), m(alph.size()) {
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };
  build(initial_state, tr, is_accept, [abs_rej_state](const state_t &s) { return s == abs_rej_state; });
 }
 template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return ret;
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  build(std::set<state_t>({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });
 }
 template <class state_t, class F, class G, class H, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const H &eps_trans): alph(alphabet), m(alph.size()) {
  static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);
  static_assert(std::is_same_v<std::set<state_t>, std::invoke_result_t<H, state_t>>);
  std::sort(alph.begin(), alph.end());
  auto eps_closure= [&](std::set<state_t> s) {
   for (std::set<state_t> t; s != t;) {
    t= s;
    for (const auto &x: t) {
     auto ys= eps_trans(x);
     s.insert(ys.begin(), ys.end());
    }
   }
   return s;
  };
  auto tr= [&](const std::set<state_t> &s, int i) {
   std::set<state_t> ret;
   for (const auto &x: s) {
    auto ys= transition(x, alph[i]);
    ret.insert(ys.begin(), ys.end());
   }
   return eps_closure(ret);
  };
  auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };
  build(eps_closure({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });
 }
 size_t alphabet_size() const { return m; }
 Automaton operator&(const Automaton &r) const {
  assert(alph == r.alph);
  const int S= info.size();
  auto tr= [&](int s, int q) {
   auto [s1, s0]= std::div(s, S);
   int t1= r.table[s1 * m + q], t0= table[s0 * m + q];
   return t0 == -1 || t1 == -1 ? -1 : t1 * S + t0;
  };
  auto ac= [&](int s) {
   auto [s1, s0]= std::div(s, S);
   return info[s0] == 1 && r.info[s1] == 1;
  };
  Automaton ret(alph);
  return ret.build(0, tr, ac, [](int s) { return s == -1; }), ret;
 }
 template <class T, class A, class F> T dp_run(int n, const A &op, const T &ti, const F &f, const T &init) const {
  static_assert(std::is_same_v<T, std::invoke_result_t<A, T, T>>);
  static_assert(std::is_same_v<T, std::invoke_result_t<F, T, symbol_t, int>>);
  const size_t S= info.size();
  std::queue<std::pair<int, int>> que;
  T dp[2][S], ret= ti;
  bool in[2][S];
  for (std::fill_n(dp[0], S, ti), std::fill_n(dp[1], S, ti), std::fill_n(in[0], S, 0), std::fill_n(in[1], S, 0), dp[0][0]= init, que.emplace(0, 0), in[0][0]= 1; que.size();) {
   auto [s, i]= que.front();
   bool b= i & 1;
   T tmp= dp[b][s];
   if (que.pop(), in[b][s]= 0, dp[b][s]= ti; i == n) {
    if (info[s] == 1) ret= op(ret, tmp);
    continue;
   }
   auto l= table.cbegin() + s * m;
   for (int j= m; j--;)
    if (int t= l[j]; t != -1)
     if (dp[!b][t]= op(dp[!b][t], f(tmp, alph[j], i)); !in[!b][t]) que.emplace(t, i + 1), in[!b][t]= 1;
  }
  return ret;
 }
 template <class T> T num(int n) const {
  return dp_run(
      n, [](const T &l, const T &r) { return l + r; }, T(), [](const T &x, const auto &, auto) { return x; }, T(1));
 }
};
using namespace std;
// https://atcoder.jp/contests/abc235/tasks/abc235_f
namespace ABC235F {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using Mint= ModInt<998244353>;
 string N;
 int M;
 cin >> N >> M;
 int n= N.length();
 int c= 0;
 for (int i= 0; i < M; i++) {
  int C;
  cin >> C, c|= 1 << C;
 }
 std::vector<int> alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr0= [&](int s, int q) {
  if (s >= n) return s;
  int c= N[s] - '0';
  if (q > c) return n + 1;
  if (q < c) return n;
  return s + 1;
 };
 auto ac0= [&](int s) { return s == n; };
 Automaton dfa_le(alp, 0, tr0, ac0, n + 1);
 auto tr1= [&](int s, int q) { return s | ((q || s) << q); };
 auto ac1= [&](int s) { return (s & c) == c; };
 Automaton dfa_variety(alp, 0, tr1, ac1);
 auto dfa= dfa_le & dfa_variety;
 using T= array<Mint, 2>;
 auto op= [](const T &l, const T &r) { return T{l[0] + r[0], l[1] + r[1]}; };
 auto f= [](const T &v, int a, int) { return T{v[0] * 10 + v[1] * a, v[1]}; };
 cout << dfa.dp_run(n, op, T{0, 0}, f, T{0, 1})[0] << '\n';
 return 0;
}
}  // namespace ABC235F
// https://atcoder.jp/contests/agc015/tasks/agc015_d
namespace AGC015D {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 vector alphabet= {0, 1};
 using state_t= set<pair<int64_t, int64_t>>;
 auto tr= [&](const state_t &S, int c) -> set<state_t> {
  set<state_t> ret;
  if (c == 0) {
   state_t T;
   bool isok= true;
   for (auto [a, b]: S) {
    if (a= (a + 1) / 2, b/= 2; a > b) {
     isok= false;
     break;
    }
    T.emplace(a, b);
   }
   if (isok) ret.insert(T);
  } else {
   int sz= S.size();
   for (int s= 1 << sz; --s;)
    for (int t= s;; --t&= s) {
     state_t T;
     bool isok= true;
     auto it= S.cbegin();
     for (int j= sz; j--; ++it) {
      auto [a, b]= *it;
      auto a0= (a + 1) / 2, b0= b / 2;
      auto a1= a / 2, b1= (b + 1) / 2 - 1;
      if ((t >> j) & 1) {
       if (a0 > b0 || a1 > b1) {
        isok= false;
        break;
       }
       T.emplace(a0, b0), T.emplace(a1, b1);
      } else if ((s >> j) & 1) {
       if (a1 > b1) {
        isok= false;
        break;
       }
       T.emplace(a1, b1);
      } else {
       if (a0 > b0) {
        isok= false;
        break;
       }
       T.emplace(a0, b0);
      }
     }
     if (isok) ret.insert(T);
     if (!t) break;
    }
  }
  return ret;
 };
 int64_t A, B;
 cin >> A >> B;
 Automaton nfa(alphabet, state_t({{A, B}}), tr, [](const auto &) { return true; });
 cout << nfa.num<int64_t>(60) << '\n';
 return 0;
}
}  // namespace AGC015D
// https://atcoder.jp/contests/abc050/tasks/arc066_b
namespace ARC066B {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<int(1e9 + 7)>;
 using symbol_t= array<bool, 2>;
 vector<symbol_t> alp= {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
 using state_t= int64_t;
 auto tr0= [&](state_t s, symbol_t c) {
  if (c[0] == 0) return s / 2;
  else return (s + 1) / 2 - 1;
 };
 auto tr1= [&](state_t s, symbol_t c) {
  if (c[1] == 0) return s / 2;
  else return (s + 1) / 2 - 1;
 };
 int64_t N;
 cin >> N;
 Automaton dfa_le0(
     alp, N, tr0, [&](int64_t) { return true; }, state_t(-1));
 Automaton dfa_le1(
     alp, N, tr1, [&](int64_t) { return true; }, state_t(-1));
 auto tr= [&](int s, symbol_t c) {
  set<int> ret;
  for (int a= 2; a--;)
   for (int b= 2; b--;)
    if ((a ^ b) == c[0] && ((a + b + s) & 1) == c[1]) ret.insert((a + b + s) / 2);
  return ret;
 };
 Automaton nfa(alp, 0, tr, [&](int s) { return s == 0; });
 auto dfa= dfa_le0 & dfa_le1 & nfa;
 cout << dfa.num<Mint>(60) << '\n';
 return 0;
}
}
// https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2587
namespace AOJ_2587 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 vector<int> low, high;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 while (cin >> N && N != 0) {
  low.resize(N), high.resize(N);
  for (int i= 0; i < N; ++i) cin >> low[i] >> high[i];
  using state_t= array<int, 2>;
  auto tr= [&](state_t s, int c) -> set<state_t> {
   auto [i, j]= s;
   if (i >= N) return {};
   auto [l1, l0]= div(low[i], 10);
   auto [h1, h0]= div(high[i], 10);
   if (j == 1) {
    if (l0 <= c) return {{i + 1, 0}};
   } else if (j == 2) return {{i + 1, 0}};
   else if (j == 3) {
    if (c <= h0) return {{i + 1, 0}};
   } else if (j == 4) {
    if (l0 <= c && c <= h0) return {{i + 1, 0}};
   } else {
    if (c == 0) return {};
    if (l1 == h1) {
     if (c == l1) return {{i, 4}};
    } else {
     if (c == l1) return {{i, 1}};
     if (l1 < c && c < h1) return {{i, 2}};
     if (c == h1) return {{i, 3}};
    }
   }
   return {};
  };
  auto eps= [&](state_t s) -> set<state_t> {
   auto [i, j]= s;
   if (i >= N) return {};
   if (j == 0 && (low[i] / 10) == 0) {
    if ((high[i] / 10) == 0) return {{i, 4}};
    else return {{i, 1}};
   }
   return {};
  };
  auto ac= [&](state_t s) { return s[0] == N && s[1] == 0; };
  Automaton nfa(alp, state_t{0, 0}, tr, ac, eps);
  int64_t ans= 0;
  for (int i= N; i <= 2 * N; ++i) ans+= nfa.num<int64_t>(i);
  cout << ans << '\n';
 }
 return 0;
}
}  // namespace AOJ_2587
// https://onlinejudge.u-aizu.ac.jp/problems/0570
namespace AOJ_0570 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<10000>;
 string A, B;
 cin >> A >> B;
 int M;
 cin >> M;
 int n= B.length();
 A= string(n - A.length(), '0') + A;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 auto tr_a= [&](int s, int c) {
  if (s >= n) return s;
  int d= A[s] - '0';
  if (c < d) return n + 1;
  if (c > d) return n;
  return s + 1;
 };
 auto tr_b= [&](int s, int c) {
  if (s >= n) return s;
  int d= B[s] - '0';
  if (c > d) return n + 1;
  if (c < d) return n;
  return s + 1;
 };
 auto ac0= [&](int s) { return s == n; };
 Automaton dfa_a(alp, 0, tr_a, ac0, n + 1), dfa_b(alp, 0, tr_b, ac0, n + 1);
 auto tr_m= [&](int s, int c) { return (s * 10 + c) % M; };
 Automaton dfa_m(alp, 0, tr_m, [](int s) { return s == 0; });
 using state_t= array<int, 2>;
 auto tr_zz= [&](state_t s, int c) -> state_t {
  auto [d, t]= s;
  if (d == -2) {
   if (c == 0) return {-2, -2};
   else return {c, -2};
  }
  if (d == c) return {-1, -1};
  if (t == -2) return {c, d < c};
  if (d < c) {
   if (t == 1) return {-1, -1};
   else return {c, 1};
  } else {
   if (t == 0) return {-1, -1};
   else return {c, 0};
  }
  return {-1, -1};
 };
 Automaton dfa_zz(
     alp, state_t{-2, -2}, tr_zz, [](state_t) { return true; }, state_t{-1, -1});

 debug(dfa_zz.num<Mint>(n));
 debug((dfa_a & dfa_b).num<Mint>(n));
 debug((dfa_a & dfa_b & dfa_m).num<Mint>(n));
 auto dfa= dfa_a & dfa_b & dfa_m & dfa_zz;
 cout << dfa.num<Mint>(n) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/315
namespace yukicoder_315 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using Mint= ModInt<int(1e9 + 7)>;
 string A, B;
 cin >> A >> B;
 int P;
 cin >> P;
 vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 vector alp3= {0, 1, 2, 4, 5, 6, 7, 8, 9};
 int t= 0;
 while (P % 10 == 0) P/= 10, ++t;
 int n_a= A.length(), n_b= B.length();
 for (int i= n_a; i--;) {
  if (A[i] > '0') {
   --A[i];
   break;
  }
  A[i]= '9';
 }
 auto tr_a= [&](int s, int c) {
  if (s >= n_a) return s;
  int d= A[s] - '0';
  if (c < d) return n_a;
  if (c > d) return n_a + 1;
  return s + 1;
 };
 auto tr_b= [&](int s, int c) {
  if (s >= n_b) return s;
  int d= B[s] - '0';
  if (c < d) return n_b;
  if (c > d) return n_b + 1;
  return s + 1;
 };
 auto ac_a= [&](int s) { return s == n_a; };
 auto ac_b= [&](int s) { return s == n_b; };
 Automaton dfa_a(alp, 0, tr_a, ac_a, n_a + 1), dfa_b(alp, 0, tr_b, ac_b, n_b + 1);
 Automaton dfa_a3(alp3, 0, tr_a, ac_a, n_a + 1), dfa_b3(alp3, 0, tr_b, ac_b, n_b + 1);
 auto tr_3= [&](int s, int c) { return (s + c) % 3; };
 Automaton dfa_3(alp3, 0, tr_3, [](int s) { return s != 0; });
 auto dfa1= dfa_a3 & dfa_3;
 auto dfa2= dfa_b3 & dfa_3;
 Mint ans= dfa_b.num<Mint>(n_b) - dfa_a.num<Mint>(n_a) - dfa2.num<Mint>(n_b) + dfa1.num<Mint>(n_a);
 n_a-= t, n_b-= t;
 Automaton dfa_a_2(alp, 0, tr_a, ac_a, n_a + 1), dfa_b_2(alp, 0, tr_b, ac_b, n_b + 1);
 Automaton dfa_a3_2(alp3, 0, tr_a, ac_a, n_a + 1), dfa_b3_2(alp3, 0, tr_b, ac_b, n_b + 1);
 auto tr_P= [&](int s, int c) { return (s * 10 + c) % P; };
 Automaton dfa_P(alp, 0, tr_P, [](int s) { return s == 0; });
 Automaton dfa_P3(alp3, 0, tr_P, [](int s) { return s == 0; });
 auto dfa3= dfa_a_2 & dfa_P;
 auto dfa4= dfa_b_2 & dfa_P;
 auto dfa5= dfa_a3_2 & (dfa_P3 & dfa_3);
 auto dfa6= dfa_b3_2 & (dfa_P3 & dfa_3);
 ans-= dfa4.num<Mint>(n_b) - dfa3.num<Mint>(n_a) - dfa6.num<Mint>(n_b) + dfa5.num<Mint>(n_a);
 cout << ans << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC235F::main();
 // AGC015D::main();
 // ARC066B::main();
 // AOJ_2587::main();
 // AOJ_0570::main();
 yukicoder_315::main();
 return 0;
}
0