結果
| 問題 | No.1417 100の倍数かつ正整数(2) |
| ユーザー |
 くれちー
|
| 提出日時 | 2021-03-05 22:55:43 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 654 ms / 3,000 ms |
| コード長 | 32,476 bytes |
| コンパイル時間 | 14,372 ms |
| コンパイル使用メモリ | 376,956 KB |
| 実行使用メモリ | 152,320 KB |
| 最終ジャッジ日時 | 2024-10-07 04:15:56 |
| 合計ジャッジ時間 | 19,166 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
コンパイルメッセージ
warning: unused imports: `Barrett`, `ButterflyCache`, `DefaultId`, `DynamicModInt`, `Id`, `Mod1000000007`, `Mod998244353`, `ModInt998244353`, `ModInt`, `Modulus`, `RemEuclidU32`, `StaticModInt`
--> src/main.rs:1044:5
|
1044 | Barrett, ButterflyCache, DefaultId, DynamicModInt, Id, Mod1000000007, Mod998244353, ModInt,
| ^^^^^^^ ^^^^^^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^^^^^ ^^ ^^^^^^^^^^^^^ ^^^^^^^^^^^^ ^^^^^^
1045 | ModInt1000000007, ModInt998244353, Modulus, RemEuclidU32, StaticModInt,
| ^^^^^^^^^^^^^^^ ^^^^^^^ ^^^^^^^^^^^^ ^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
ソースコード
// The main code is at the very bottom.
#[allow(unused_imports)]
use {
lib::byte::ByteChar,
std::cell::{Cell, RefCell},
std::cmp::{
self,
Ordering::{self, *},
Reverse,
},
std::collections::*,
std::convert::identity,
std::fmt::{self, Debug, Display, Formatter},
std::io::prelude::*,
std::iter::{self, FromIterator},
std::marker::PhantomData,
std::mem,
std::num::Wrapping,
std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},
std::process,
std::rc::Rc,
std::thread,
std::time::{Duration, Instant},
std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},
};
#[allow(unused_imports)]
#[macro_use]
pub mod lib {
pub mod byte {
pub use self::byte_char::*;
mod byte_char {
use std::error::Error;
use std::fmt::{self, Debug, Display, Formatter};
use std::str::FromStr;
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct ByteChar(pub u8);
impl Debug for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "b'{}'", self.0 as char)
}
}
impl Display for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}", self.0 as char)
}
}
impl FromStr for ByteChar {
type Err = ParseByteCharError;
fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {
match s.as_bytes().len() {
1 => Ok(ByteChar(s.as_bytes()[0])),
0 => Err(ParseByteCharErrorKind::EmptyStr.into()),
_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct ParseByteCharError {
kind: ParseByteCharErrorKind,
}
impl Display for ParseByteCharError {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.write_str(match self.kind {
ParseByteCharErrorKind::EmptyStr => "empty string",
ParseByteCharErrorKind::TooManyBytes => "too many bytes",
})
}
}
impl Error for ParseByteCharError {}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum ParseByteCharErrorKind {
EmptyStr,
TooManyBytes,
}
impl From<ParseByteCharErrorKind> for ParseByteCharError {
fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {
ParseByteCharError { kind }
}
}
}
}
pub mod io {
pub use self::scanner::*;
mod scanner {
use std::io::{self, BufRead};
use std::iter;
use std::str::FromStr;
#[derive(Debug)]
pub struct Scanner<R> {
reader: R,
buf: String,
pos: usize,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Scanner {
reader,
buf: String::new(),
pos: 0,
}
}
pub fn next(&mut self) -> io::Result<&str> {
let start = loop {
match self.rest().find(|c| c != ' ') {
Some(i) => break i,
None => self.fill_buf()?,
}
};
self.pos += start;
let len = self.rest().find(' ').unwrap_or(self.rest().len());
let s = &self.buf[self.pos..][..len]; // self.rest()[..len]
self.pos += len;
Ok(s)
}
pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>
where
T: FromStr,
{
Ok(self.next()?.parse())
}
pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>
where
T: FromStr,
{
iter::repeat_with(|| self.parse_next()).take(n).collect()
}
pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>
where
F: FnMut(u8) -> T,
{
Ok(self.next()?.bytes().map(&mut f).collect())
}
pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>
where
F: FnMut(u8) -> T,
{
iter::repeat_with(|| self.map_next_bytes(&mut f))
.take(n)
.collect()
}
fn rest(&self) -> &str {
&self.buf[self.pos..]
}
fn fill_buf(&mut self) -> io::Result<()> {
self.buf.clear();
self.pos = 0;
let read = self.reader.read_line(&mut self.buf)?;
if read == 0 {
return Err(io::ErrorKind::UnexpectedEof.into());
}
if *self.buf.as_bytes().last().unwrap() == b'\n' {
self.buf.pop();
}
Ok(())
}
}
}
}
}
#[allow(dead_code)]
mod ac_library_rs {
pub mod modint {
use crate::ac_library_rs::internal_math;
use std::{
cell::RefCell,
convert::{Infallible, TryInto as _},
fmt,
hash::{Hash, Hasher},
iter::{Product, Sum},
marker::PhantomData,
ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
str::FromStr,
sync::atomic::{self, AtomicU32, AtomicU64},
thread::LocalKey,
};
pub type ModInt1000000007 = StaticModInt<Mod1000000007>;
pub type ModInt998244353 = StaticModInt<Mod998244353>;
pub type ModInt = DynamicModInt<DefaultId>;
#[derive(Copy, Clone, Eq, PartialEq)]
#[repr(transparent)]
pub struct StaticModInt<M> {
val: u32,
phantom: PhantomData<fn() -> M>,
}
impl<M: Modulus> StaticModInt<M> {
#[inline(always)]
pub fn modulus() -> u32 {
M::VALUE
}
#[inline]
pub fn new<T: RemEuclidU32>(val: T) -> Self {
Self::raw(val.rem_euclid_u32(M::VALUE))
}
#[inline]
pub fn raw(val: u32) -> Self {
Self {
val,
phantom: PhantomData,
}
}
#[inline]
pub fn val(self) -> u32 {
self.val
}
#[inline]
pub fn pow(self, n: u64) -> Self {
<Self as ModIntBase>::pow(self, n)
}
#[inline]
pub fn inv(self) -> Self {
if M::HINT_VALUE_IS_PRIME {
if self.val() == 0 {
panic!("attempt to divide by zero");
}
debug_assert!(
internal_math::is_prime(M::VALUE.try_into().unwrap()),
"{} is not a prime number",
M::VALUE,
);
self.pow((M::VALUE - 2).into())
} else {
Self::inv_for_non_prime_modulus(self)
}
}
}
impl<M: Modulus> ModIntBase for StaticModInt<M> {
#[inline(always)]
fn modulus() -> u32 {
Self::modulus()
}
#[inline]
fn raw(val: u32) -> Self {
Self::raw(val)
}
#[inline]
fn val(self) -> u32 {
self.val()
}
#[inline]
fn inv(self) -> Self {
self.inv()
}
}
pub trait Modulus: 'static + Copy + Eq {
const VALUE: u32;
const HINT_VALUE_IS_PRIME: bool;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
}
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum Mod1000000007 {}
impl Modulus for Mod1000000007 {
const VALUE: u32 = 1_000_000_007;
const HINT_VALUE_IS_PRIME: bool = true;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: RefCell<Option<ButterflyCache<Mod1000000007>>> = RefCell::default();
}
&BUTTERFLY_CACHE
}
}
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum Mod998244353 {}
impl Modulus for Mod998244353 {
const VALUE: u32 = 998_244_353;
const HINT_VALUE_IS_PRIME: bool = true;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: RefCell<Option<ButterflyCache<Mod998244353>>> = RefCell::default();
}
&BUTTERFLY_CACHE
}
}
pub struct ButterflyCache<M> {
pub(crate) sum_e: Vec<StaticModInt<M>>,
pub(crate) sum_ie: Vec<StaticModInt<M>>,
}
#[derive(Copy, Clone, Eq, PartialEq)]
#[repr(transparent)]
pub struct DynamicModInt<I> {
val: u32,
phantom: PhantomData<fn() -> I>,
}
impl<I: Id> DynamicModInt<I> {
#[inline]
pub fn modulus() -> u32 {
I::companion_barrett().umod()
}
#[inline]
pub fn set_modulus(modulus: u32) {
if modulus == 0 {
panic!("the modulus must not be 0");
}
I::companion_barrett().update(modulus);
}
#[inline]
pub fn new<T: RemEuclidU32>(val: T) -> Self {
<Self as ModIntBase>::new(val)
}
#[inline]
pub fn raw(val: u32) -> Self {
Self {
val,
phantom: PhantomData,
}
}
#[inline]
pub fn val(self) -> u32 {
self.val
}
#[inline]
pub fn pow(self, n: u64) -> Self {
<Self as ModIntBase>::pow(self, n)
}
#[inline]
pub fn inv(self) -> Self {
Self::inv_for_non_prime_modulus(self)
}
}
impl<I: Id> ModIntBase for DynamicModInt<I> {
#[inline]
fn modulus() -> u32 {
Self::modulus()
}
#[inline]
fn raw(val: u32) -> Self {
Self::raw(val)
}
#[inline]
fn val(self) -> u32 {
self.val()
}
#[inline]
fn inv(self) -> Self {
self.inv()
}
}
pub trait Id: 'static + Copy + Eq {
fn companion_barrett() -> &'static Barrett;
}
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash, Debug)]
pub enum DefaultId {}
impl Id for DefaultId {
fn companion_barrett() -> &'static Barrett {
static BARRETT: Barrett = Barrett::default();
&BARRETT
}
}
pub struct Barrett {
m: AtomicU32,
im: AtomicU64,
}
impl Barrett {
#[inline]
pub const fn new(m: u32) -> Self {
Self {
m: AtomicU32::new(m),
im: AtomicU64::new((-1i64 as u64 / m as u64).wrapping_add(1)),
}
}
#[inline]
const fn default() -> Self {
Self::new(998_244_353)
}
#[inline]
fn update(&self, m: u32) {
let im = (-1i64 as u64 / m as u64).wrapping_add(1);
self.m.store(m, atomic::Ordering::SeqCst);
self.im.store(im, atomic::Ordering::SeqCst);
}
#[inline]
fn umod(&self) -> u32 {
self.m.load(atomic::Ordering::SeqCst)
}
#[inline]
fn mul(&self, a: u32, b: u32) -> u32 {
let m = self.m.load(atomic::Ordering::SeqCst);
let im = self.im.load(atomic::Ordering::SeqCst);
internal_math::mul_mod(a, b, m, im)
}
}
impl Default for Barrett {
#[inline]
fn default() -> Self {
Self::default()
}
}
pub trait ModIntBase:
Default
+ FromStr
+ From<i8>
+ From<i16>
+ From<i32>
+ From<i64>
+ From<i128>
+ From<isize>
+ From<u8>
+ From<u16>
+ From<u32>
+ From<u64>
+ From<u128>
+ From<usize>
+ Copy
+ Eq
+ Hash
+ fmt::Display
+ fmt::Debug
+ Neg<Output = Self>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
{
fn modulus() -> u32;
fn raw(val: u32) -> Self;
fn val(self) -> u32;
fn inv(self) -> Self;
#[inline]
fn new<T: RemEuclidU32>(val: T) -> Self {
Self::raw(val.rem_euclid_u32(Self::modulus()))
}
#[inline]
fn pow(self, mut n: u64) -> Self {
let mut x = self;
let mut r = Self::raw(1);
while n > 0 {
if n & 1 == 1 {
r *= x;
}
x *= x;
n >>= 1;
}
r
}
}
pub trait RemEuclidU32 {
fn rem_euclid_u32(self, modulus: u32) -> u32;
}
macro_rules! impl_rem_euclid_u32_for_small_signed {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
(self as i64).rem_euclid(i64::from(modulus)) as _
}
}
)*
}
}
impl_rem_euclid_u32_for_small_signed!(i8, i16, i32, i64, isize);
impl RemEuclidU32 for i128 {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
self.rem_euclid(i128::from(modulus)) as _
}
}
macro_rules! impl_rem_euclid_u32_for_small_unsigned {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
self as u32 % modulus
}
}
)*
}
}
macro_rules! impl_rem_euclid_u32_for_large_unsigned {
($($ty:tt),*) => {
$(
impl RemEuclidU32 for $ty {
#[inline]
fn rem_euclid_u32(self, modulus: u32) -> u32 {
(self % (modulus as $ty)) as _
}
}
)*
}
}
impl_rem_euclid_u32_for_small_unsigned!(u8, u16, u32);
impl_rem_euclid_u32_for_large_unsigned!(u64, u128);
#[cfg(target_pointer_width = "32")]
impl_rem_euclid_u32_for_small_unsigned!(usize);
#[cfg(target_pointer_width = "64")]
impl_rem_euclid_u32_for_large_unsigned!(usize);
trait InternalImplementations: ModIntBase {
#[inline]
fn inv_for_non_prime_modulus(this: Self) -> Self {
let (gcd, x) = internal_math::inv_gcd(this.val().into(), Self::modulus().into());
if gcd != 1 {
panic!("the multiplicative inverse does not exist");
}
Self::new(x)
}
#[inline]
fn default_impl() -> Self {
Self::raw(0)
}
#[inline]
fn from_str_impl(s: &str) -> Result<Self, Infallible> {
Ok(
s.parse::<i64>()
.map(Self::new)
.unwrap_or_else(|_| todo!("parsing as an arbitrary precision integer?")),
)
}
#[inline]
fn hash_impl(this: &Self, state: &mut impl Hasher) {
this.val().hash(state)
}
#[inline]
fn display_impl(this: &Self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Display::fmt(&this.val(), f)
}
#[inline]
fn debug_impl(this: &Self, f: &mut fmt::Formatter) -> fmt::Result {
fmt::Debug::fmt(&this.val(), f)
}
#[inline]
fn neg_impl(this: Self) -> Self {
Self::sub_impl(Self::raw(0), this)
}
#[inline]
fn add_impl(lhs: Self, rhs: Self) -> Self {
let modulus = Self::modulus();
let mut val = lhs.val() + rhs.val();
if val >= modulus {
val -= modulus;
}
Self::raw(val)
}
#[inline]
fn sub_impl(lhs: Self, rhs: Self) -> Self {
let modulus = Self::modulus();
let mut val = lhs.val().wrapping_sub(rhs.val());
if val >= modulus {
val = val.wrapping_add(modulus)
}
Self::raw(val)
}
fn mul_impl(lhs: Self, rhs: Self) -> Self;
#[inline]
fn div_impl(lhs: Self, rhs: Self) -> Self {
Self::mul_impl(lhs, rhs.inv())
}
}
impl<M: Modulus> InternalImplementations for StaticModInt<M> {
#[inline]
fn mul_impl(lhs: Self, rhs: Self) -> Self {
Self::raw((u64::from(lhs.val()) * u64::from(rhs.val()) % u64::from(M::VALUE)) as u32)
}
}
impl<I: Id> InternalImplementations for DynamicModInt<I> {
#[inline]
fn mul_impl(lhs: Self, rhs: Self) -> Self {
Self::raw(I::companion_barrett().mul(lhs.val, rhs.val))
}
}
macro_rules! impl_basic_traits {
() => {};
(impl <$generic_param:ident : $generic_param_bound:tt> _ for $self:ty; $($rest:tt)*) => {
impl <$generic_param: $generic_param_bound> Default for $self {
#[inline]
fn default() -> Self {
Self::default_impl()
}
}
impl <$generic_param: $generic_param_bound> FromStr for $self {
type Err = Infallible;
#[inline]
fn from_str(s: &str) -> Result<Self, Infallible> {
Self::from_str_impl(s)
}
}
impl<$generic_param: $generic_param_bound, V: RemEuclidU32> From<V> for $self {
#[inline]
fn from(from: V) -> Self {
Self::new(from)
}
}
#[allow(clippy::derive_hash_xor_eq)]
impl<$generic_param: $generic_param_bound> Hash for $self {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
Self::hash_impl(self, state)
}
}
impl<$generic_param: $generic_param_bound> fmt::Display for $self {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Self::display_impl(self, f)
}
}
impl<$generic_param: $generic_param_bound> fmt::Debug for $self {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Self::debug_impl(self, f)
}
}
impl<$generic_param: $generic_param_bound> Neg for $self {
type Output = $self;
#[inline]
fn neg(self) -> $self {
Self::neg_impl(self)
}
}
impl<$generic_param: $generic_param_bound> Neg for &'_ $self {
type Output = $self;
#[inline]
fn neg(self) -> $self {
<$self>::neg_impl(*self)
}
}
impl_basic_traits!($($rest)*);
};
}
impl_basic_traits! {
impl <M: Modulus> _ for StaticModInt<M> ;
impl <I: Id > _ for DynamicModInt<I>;
}
macro_rules! impl_bin_ops {
() => {};
(for<$($generic_param:ident : $generic_param_bound:tt),*> <$lhs_ty:ty> ~ <$rhs_ty:ty> -> $output:ty { { $lhs_body:expr } ~ { $rhs_body:expr } } $($rest:tt)*) => {
impl <$($generic_param: $generic_param_bound),*> Add<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn add(self, rhs: $rhs_ty) -> $output {
<$output>::add_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Sub<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn sub(self, rhs: $rhs_ty) -> $output {
<$output>::sub_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Mul<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn mul(self, rhs: $rhs_ty) -> $output {
<$output>::mul_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl <$($generic_param: $generic_param_bound),*> Div<$rhs_ty> for $lhs_ty {
type Output = $output;
#[inline]
fn div(self, rhs: $rhs_ty) -> $output {
<$output>::div_impl(apply($lhs_body, self), apply($rhs_body, rhs))
}
}
impl_bin_ops!($($rest)*);
};
}
macro_rules! impl_assign_ops {
() => {};
(for<$($generic_param:ident : $generic_param_bound:tt),*> <$lhs_ty:ty> ~= <$rhs_ty:ty> { _ ~= { $rhs_body:expr } } $($rest:tt)*) => {
impl <$($generic_param: $generic_param_bound),*> AddAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn add_assign(&mut self, rhs: $rhs_ty) {
*self = *self + apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> SubAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn sub_assign(&mut self, rhs: $rhs_ty) {
*self = *self - apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> MulAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn mul_assign(&mut self, rhs: $rhs_ty) {
*self = *self * apply($rhs_body, rhs);
}
}
impl <$($generic_param: $generic_param_bound),*> DivAssign<$rhs_ty> for $lhs_ty {
#[inline]
fn div_assign(&mut self, rhs: $rhs_ty) {
*self = *self / apply($rhs_body, rhs);
}
}
impl_assign_ops!($($rest)*);
};
}
#[inline]
fn apply<F: FnOnce(X) -> O, X, O>(f: F, x: X) -> O {
f(x)
}
impl_bin_ops! {
for<M: Modulus> <StaticModInt<M> > ~ <StaticModInt<M> > -> StaticModInt<M> { { |x| x } ~ { |x| x } }
for<M: Modulus> <StaticModInt<M> > ~ <&'_ StaticModInt<M> > -> StaticModInt<M> { { |x| x } ~ { |&x| x } }
for<M: Modulus> <&'_ StaticModInt<M> > ~ <StaticModInt<M> > -> StaticModInt<M> { { |&x| x } ~ { |x| x } }
for<M: Modulus> <&'_ StaticModInt<M> > ~ <&'_ StaticModInt<M> > -> StaticModInt<M> { { |&x| x } ~ { |&x| x } }
for<I: Id > <DynamicModInt<I> > ~ <DynamicModInt<I> > -> DynamicModInt<I> { { |x| x } ~ { |x| x } }
for<I: Id > <DynamicModInt<I> > ~ <&'_ DynamicModInt<I>> -> DynamicModInt<I> { { |x| x } ~ { |&x| x } }
for<I: Id > <&'_ DynamicModInt<I>> ~ <DynamicModInt<I> > -> DynamicModInt<I> { { |&x| x } ~ { |x| x } }
for<I: Id > <&'_ DynamicModInt<I>> ~ <&'_ DynamicModInt<I>> -> DynamicModInt<I> { { |&x| x } ~ { |&x| x } }
for<M: Modulus, T: RemEuclidU32> <StaticModInt<M> > ~ <T> -> StaticModInt<M> { { |x| x } ~ { StaticModInt::<M>::new } }
for<I: Id , T: RemEuclidU32> <DynamicModInt<I> > ~ <T> -> DynamicModInt<I> { { |x| x } ~ { DynamicModInt::<I>::new } }
}
impl_assign_ops! {
for<M: Modulus> <StaticModInt<M> > ~= <StaticModInt<M> > { _ ~= { |x| x } }
for<M: Modulus> <StaticModInt<M> > ~= <&'_ StaticModInt<M> > { _ ~= { |&x| x } }
for<I: Id > <DynamicModInt<I>> ~= <DynamicModInt<I> > { _ ~= { |x| x } }
for<I: Id > <DynamicModInt<I>> ~= <&'_ DynamicModInt<I>> { _ ~= { |&x| x } }
for<M: Modulus, T: RemEuclidU32> <StaticModInt<M> > ~= <T> { _ ~= { StaticModInt::<M>::new } }
for<I: Id, T: RemEuclidU32> <DynamicModInt<I>> ~= <T> { _ ~= { DynamicModInt::<I>::new } }
}
macro_rules! impl_folding {
() => {};
(impl<$generic_param:ident : $generic_param_bound:tt> $trait:ident<_> for $self:ty { fn $method:ident(_) -> _ { _($unit:expr, $op:expr) } } $($rest:tt)*) => {
impl<$generic_param: $generic_param_bound> $trait<Self> for $self {
#[inline]
fn $method<S>(iter: S) -> Self
where
S: Iterator<Item = Self>,
{
iter.fold($unit, $op)
}
}
impl<'a, $generic_param: $generic_param_bound> $trait<&'a Self> for $self {
#[inline]
fn $method<S>(iter: S) -> Self
where
S: Iterator<Item = &'a Self>,
{
iter.fold($unit, $op)
}
}
impl_folding!($($rest)*);
};
}
impl_folding! {
impl<M: Modulus> Sum<_> for StaticModInt<M> { fn sum(_) -> _ { _(Self::raw(0), Add::add) } }
impl<M: Modulus> Product<_> for StaticModInt<M> { fn product(_) -> _ { _(Self::raw(1), Mul::mul) } }
impl<I: Id > Sum<_> for DynamicModInt<I> { fn sum(_) -> _ { _(Self::raw(0), Add::add) } }
impl<I: Id > Product<_> for DynamicModInt<I> { fn product(_) -> _ { _(Self::raw(1), Mul::mul) } }
}
}
pub(crate) mod internal_math {
#![allow(dead_code)]
use std::mem::swap;
pub(crate) fn safe_mod(mut x: i64, m: i64) -> i64 {
x %= m;
if x < 0 {
x += m;
}
x
}
pub(crate) struct Barrett {
pub(crate) _m: u32,
pub(crate) im: u64,
}
impl Barrett {
pub(crate) fn new(m: u32) -> Barrett {
Barrett {
_m: m,
im: (-1i64 as u64 / m as u64).wrapping_add(1),
}
}
pub(crate) fn umod(&self) -> u32 {
self._m
}
#[allow(clippy::many_single_char_names)]
pub(crate) fn mul(&self, a: u32, b: u32) -> u32 {
mul_mod(a, b, self._m, self.im)
}
}
#[allow(clippy::many_single_char_names)]
pub(crate) fn mul_mod(a: u32, b: u32, m: u32, im: u64) -> u32 {
let mut z = a as u64;
z *= b as u64;
let x = (((z as u128) * (im as u128)) >> 64) as u64;
let mut v = z.wrapping_sub(x.wrapping_mul(m as u64)) as u32;
if m <= v {
v = v.wrapping_add(m);
}
v
}
#[allow(clippy::many_single_char_names)]
pub(crate) fn pow_mod(x: i64, mut n: i64, m: i32) -> i64 {
if m == 1 {
return 0;
}
let _m = m as u32;
let mut r: u64 = 1;
let mut y: u64 = safe_mod(x, m as i64) as u64;
while n != 0 {
if (n & 1) > 0 {
r = (r * y) % (_m as u64);
}
y = (y * y) % (_m as u64);
n >>= 1;
}
r as i64
}
pub(crate) fn is_prime(n: i32) -> bool {
let n = n as i64;
match n {
_ if n <= 1 => return false,
2 | 7 | 61 => return true,
_ if n % 2 == 0 => return false,
_ => {}
}
let mut d = n - 1;
while d % 2 == 0 {
d /= 2;
}
for &a in &[2, 7, 61] {
let mut t = d;
let mut y = pow_mod(a, t, n as i32);
while t != n - 1 && y != 1 && y != n - 1 {
y = y * y % n;
t <<= 1;
}
if y != n - 1 && t % 2 == 0 {
return false;
}
}
true
}
#[allow(clippy::many_single_char_names)]
pub(crate) fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
let a = safe_mod(a, b);
if a == 0 {
return (b, 0);
}
let mut s = b;
let mut t = a;
let mut m0 = 0;
let mut m1 = 1;
while t != 0 {
let u = s / t;
s -= t * u;
m0 -= m1 * u;
swap(&mut s, &mut t);
swap(&mut m0, &mut m1);
}
if m0 < 0 {
m0 += b / s;
}
(s, m0)
}
pub(crate) fn primitive_root(m: i32) -> i32 {
match m {
2 => return 1,
167_772_161 => return 3,
469_762_049 => return 3,
754_974_721 => return 11,
998_244_353 => return 3,
_ => {}
}
let mut divs = [0; 20];
divs[0] = 2;
let mut cnt = 1;
let mut x = (m - 1) / 2;
while x % 2 == 0 {
x /= 2;
}
for i in (3..std::i32::MAX).step_by(2) {
if i as i64 * i as i64 > x as i64 {
break;
}
if x % i == 0 {
divs[cnt] = i;
cnt += 1;
while x % i == 0 {
x /= i;
}
}
}
if x > 1 {
divs[cnt] = x;
cnt += 1;
}
let mut g = 2;
loop {
if (0..cnt).all(|i| pow_mod(g, ((m - 1) / divs[i]) as i64, m) != 1) {
break g as i32;
}
g += 1;
}
}
}
pub use modint::{
Barrett, ButterflyCache, DefaultId, DynamicModInt, Id, Mod1000000007, Mod998244353, ModInt,
ModInt1000000007, ModInt998244353, Modulus, RemEuclidU32, StaticModInt,
};
}
#[allow(unused_macros)]
macro_rules! eprint {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprint!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! eprintln {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprintln!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! dbg {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::dbg!($($arg)*)
} else {
($($arg)*)
}
};
}
const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);
const INTERACTIVE: bool = false;
fn main() -> std::io::Result<()> {
match CUSTOM_STACK_SIZE_MIB {
Some(stack_size_mib) => std::thread::Builder::new()
.name("run_solver".to_owned())
.stack_size(stack_size_mib * 1024 * 1024)
.spawn(run_solver)?
.join()
.unwrap(),
None => run_solver(),
}
}
fn run_solver() -> std::io::Result<()> {
let stdin = std::io::stdin();
let reader = stdin.lock();
let stdout = std::io::stdout();
let writer = stdout.lock();
macro_rules! with_wrapper {
($($wrapper:expr)?) => {{
let mut writer = $($wrapper)?(writer);
solve(reader, &mut writer)?;
writer.flush()
}};
}
if cfg!(debug_assertions) || INTERACTIVE {
with_wrapper!()
} else {
with_wrapper!(std::io::BufWriter::new)
}
}
fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>
where
R: BufRead,
W: Write,
{
let mut _scanner = lib::io::Scanner::new(reader);
#[allow(unused_macros)]
macro_rules! scan {
($T:ty) => {
_scanner.parse_next::<$T>()?.unwrap()
};
($($T:ty),+) => {
($(scan!($T)),+)
};
($T:ty; $n:expr) => {
_scanner.parse_next_n::<$T>($n)?.unwrap()
};
($($T:ty),+; $n:expr) => {
iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) })
.take($n)
.collect::<std::io::Result<Vec<_>>>()?
};
}
#[allow(unused_macros)]
macro_rules! scan_bytes_map {
($f:expr) => {
_scanner.map_next_bytes($f)?
};
($f:expr; $n:expr) => {
_scanner.map_next_bytes_n($n, $f)?
};
}
#[allow(unused_macros)]
macro_rules! print {
($($arg:tt)*) => {
write!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! println {
($($arg:tt)*) => {
writeln!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! answer {
($($arg:tt)*) => {{
println!($($arg)*);
return Ok(());
}};
}
{
use ac_library_rs::ModInt1000000007 as Mint;
let n = scan_bytes_map!(|d| d - b'0');
let mut dp = vec![vec![vec![vec![Mint::new(0); 3]; 2]; 101]; n.len() + 1];
dp[0][100][0][0] = Mint::new(1);
for i in 1..=n.len() {
// p = 0..100: digit product, 100: only leading zeros
for p in 0..101u32 {
for z in 0..2 {
// f = 0: tight, 1: loose, 2: exceeded
for f in 0..3 {
for d in 0..10u8 {
let p_next = if p == 100 {
if d == 0 {
100
} else {
d as u32
}
} else {
(p * d as u32) % 100
};
let z_next = if z == 1 || p != 100 && d == 0 { 1 } else { 0 };
let f_next = match f {
0 => match d.cmp(&n[i - 1]) {
Less => 1,
Equal => 0,
Greater => 2,
},
f => f,
};
let t = dp[i - 1][p as usize][z][f];
dp[i][p_next as usize][z_next][f_next] += t;
}
}
}
}
}
let mut acc = Mint::new(0);
{
let i = n.len();
let p = 0;
let z = 0;
for f in 0..2 {
acc += dp[i][p][z][f];
}
}
println!("{}", acc);
}
#[allow(unreachable_code)]
Ok(())
}