#![allow(unused_imports, non_snake_case)] #![allow(dead_code)] use crate::{ arraylist::List, ext::{iter::IterExtra, string::CharExtra}, scanner::Scanner, }; modint!(); fn main() { let mut scan = Scanner::new(); let mut n = scan.chars(); n.reverse(); let mut z = Z::new(45); let mut w = Z::new((1..=n[0].sub_i64('0')).sumint()); let mut x = Z::new(0); for i in 1..n.lens() { x += z; w = z * (1..n[i].sub_i64('0')).sumint().into() + w * n[i].sub_i64('0').into(); z *= 45.into(); } println!("{}", w + x); } pub mod ext { pub mod iter { use crate::{arraylist::List, independent::integer::Int}; pub trait IterExtra: Iterator + Sized { fn list(self) -> List { self.collect() } fn to>(self) -> B { self.collect() } fn counti(self) -> isize { self.count() as isize } fn enumeratei( self, ) -> std::iter::Map< std::iter::Enumerate, fn((usize, Self::Item)) -> (isize, Self::Item), > { self.enumerate().map(|t| (t.0 as isize, t.1)) } fn sumint(self) -> Self::Item where Self::Item: Int, { self.fold(Self::Item::zero(), |acc, x| acc + x) } fn min_exn(self) -> Self::Item where Self::Item: Ord, { self.min().unwrap() } fn max_exn(self) -> Self::Item where Self::Item: Ord, { self.max().unwrap() } } impl IterExtra for T where T: Iterator {} } pub mod string { use crate::{arraylist::List, independent::integer::Int}; pub trait StringExtra { fn to_chars(self) -> List; } impl StringExtra for String { fn to_chars(self) -> List { self.chars().collect() } } pub trait CharExtra { fn sub(self, b: char) -> isize; fn sub_i64(self, b: char) -> i64; #[doc = " [start, end]"] fn in_range(self, start: char, end: char) -> bool; fn add(self, d: T) -> char; } impl CharExtra for char { fn sub(self, b: char) -> isize { self as isize - b as isize } fn sub_i64(self, b: char) -> i64 { self as i64 - b as i64 } fn in_range(self, start: char, end: char) -> bool { (start as u8..=end as u8).contains(&(self as u8)) } fn add(self, d: T) -> char { (d.to_u8() + self as u8) as char } } } pub mod range { use crate::independent::integer::Int; use std::cmp::{max, min}; use std::ops::{Bound, Range, RangeBounds}; pub trait IntRangeBounds: RangeBounds { fn lbopt(&self) -> Option { match self.start_bound() { Bound::Included(x) => Some(*x), Bound::Excluded(x) => Some(*x + U::one()), Bound::Unbounded => None, } } fn ubopt(&self) -> Option { match self.end_bound() { Bound::Included(x) => Some(*x + U::one()), Bound::Excluded(x) => Some(*x), Bound::Unbounded => None, } } #[doc = " inclusive"] fn lower_bound(&self, limit: U) -> U { self.lbopt().map_or(limit, |x| max(limit, x)) } #[doc = " exclusive"] fn upper_bound(&self, limit: U) -> U { self.ubopt().map_or(limit, |x| min(limit, x)) } fn to_harfopen(&self, lb: U, ub: U) -> Range { self.lower_bound(lb)..self.upper_bound(ub) } fn within(&self, mut t: U) -> U { if let Some(x) = self.lbopt() { if t < x { t = x; } } if let Some(x) = self.ubopt() { if x <= t { t = x - U::one(); } } t } fn width(&self) -> U { if self.empty() { U::zero() } else { self.ubopt().unwrap() - self.lbopt().unwrap() } } fn empty(&self) -> bool { self.lbopt().is_none() || self.ubopt().is_none() || !(self.lbopt().unwrap() < self.ubopt().unwrap()) } fn contain_range(&self, inner: &Self) -> bool { (match (self.lbopt(), inner.lbopt()) { (Some(a), Some(b)) => a <= b, (None, _) => true, (Some(_), None) => false, }) && (match (inner.ubopt(), self.ubopt()) { (Some(a), Some(b)) => a <= b, (_, None) => true, (None, Some(_)) => false, }) } fn separate_range(&self, other: &Self) -> bool { if let (Some(a), Some(b)) = (self.ubopt(), other.lbopt()) { if a <= b { return true; } } if let (Some(a), Some(b)) = (other.ubopt(), self.lbopt()) { if a <= b { return true; } } false } fn overlap(&self, other: &Self) -> Range { let left = if let (Some(a), Some(b)) = (self.lbopt(), other.lbopt()) { max(a, b) } else { self.lbopt().or(other.lbopt()).unwrap() }; let right = if let (Some(a), Some(b)) = (self.ubopt(), other.ubopt()) { min(a, b) } else { self.ubopt().or(other.ubopt()).unwrap() }; left..right } } impl IntRangeBounds for T where T: RangeBounds {} } } pub mod arraylist { use crate::{ext::range::IntRangeBounds, independent::integer::Int}; use std::fmt::Formatter; use std::iter::FromIterator; use std::ops::{Index, IndexMut, RangeBounds}; use std::slice::Iter; #[derive(Clone, PartialEq, Eq)] pub struct List { pub vec: Vec, } impl List { #[inline] pub fn new() -> List { List { vec: vec![] } } #[inline] pub fn init(init: T, n: isize) -> List where T: Clone, { List { vec: vec![init; n as usize], } } #[inline] pub fn from_vec(vec: Vec) -> List { List { vec } } #[inline] pub fn acc<'a, S>(n: isize, mut f: S) -> List where S: FnMut(isize) -> T + 'a, { (0..n).map(|i| f(i)).collect() } #[inline] pub fn lens(&self) -> isize { self.vec.len() as isize } #[inline] pub fn iter(&self) -> Iter<'_, T> { self.vec.iter() } #[inline] pub fn push(&mut self, item: T) { self.vec.push(item); } #[inline] pub fn sort(&mut self) where T: Ord, { self.vec.sort(); } #[inline] pub fn reverse(&mut self) { self.vec.reverse(); } #[inline] pub fn sort_by(&mut self, compare: F) where F: FnMut(&T, &T) -> std::cmp::Ordering, { self.vec.sort_by(compare) } #[inline] pub fn sort_by_key(&mut self, compare: F) where F: FnMut(&T) -> K, K: Ord, { self.vec.sort_by_key(compare) } #[inline] pub fn first(&self) -> Option<&T> { self.vec.first() } #[inline] pub fn last(&self) -> Option<&T> { self.vec.last() } #[inline] pub fn pop(&mut self) -> Option { self.vec.pop() } #[inline] pub fn swap(&mut self, i: isize, j: isize) { self.vec.swap(i as usize, j as usize); } #[inline] pub fn append(&mut self, mut other: Self) { self.vec.append(&mut other.vec); } #[inline] pub fn extend(&mut self, other: impl Iterator) { self.vec.extend(other); } #[inline] pub fn mrr(&self) -> std::iter::Cloned> where T: Clone, { self.iter().cloned() } #[inline] pub fn join(&self, sep: &str) -> String where T: std::fmt::Display, { self.iter() .map(|x| format!("{}", x)) .collect::>() .join(sep) } #[inline] pub fn map(&self, f: F) -> List where T: Clone, F: FnMut(T) -> B, { self.mrr().map(f).collect() } #[inline] pub fn filter

(&self, predicate: P) -> List where T: Clone, P: FnMut(&T) -> bool, { self.mrr().filter(predicate).collect() } #[inline] pub fn filter_map(&self, f: F) -> List where T: Clone, F: FnMut(T) -> Option, { self.mrr().filter_map(f).collect() } #[doc = " |acc, x| -> acc"] #[inline] pub fn fold(&self, init: B, f: F) -> B where T: Clone, F: FnMut(B, T) -> B, { self.mrr().fold(init, f) } #[inline] pub fn any

(&self, predicate: P) -> bool where P: FnMut(&T) -> bool, { self.iter().any(predicate) } #[inline] pub fn all

(&self, predicate: P) -> bool where P: FnMut(&T) -> bool, { self.iter().all(predicate) } #[inline] pub fn sum(&self) -> T where T: Int, { self.iter().cloned().fold(T::zero(), |acc, x| acc + x) } #[inline] pub fn enumerate(&self) -> List<(isize, T)> where T: Clone, { self.mrr() .enumerate() .map(|p| (p.0 as isize, p.1)) .collect() } #[inline] pub fn find

(&self, mut predicate: P) -> Option<&T> where P: FnMut(&T) -> bool, { self.iter().find(|x| predicate(*x)) } #[inline] pub fn index_of

(&self, mut predicate: P) -> Option where P: FnMut(&T) -> bool, { self.iter() .enumerate() .find(|&(_i, x)| predicate(x)) .map(|p| p.0 as isize) } #[inline] pub fn to>(&self) -> B where T: Clone, { self.mrr().collect() } #[inline] pub fn min(&self) -> Option<&T> where T: Ord, { self.iter().min() } #[inline] pub fn max(&self) -> Option<&T> where T: Ord, { self.iter().max() } #[inline] pub fn argmin(&self) -> Option where T: Ord, { let item = self.iter().min()?; self.iter() .enumerate() .find(|p| p.1 == item) .map(|p| p.0 as isize) } #[inline] pub fn argmax(&self) -> Option where T: Ord, { let item = self.iter().max()?; self.iter() .enumerate() .find(|p| p.1 == item) .map(|p| p.0 as isize) } #[inline] pub fn part(&self, range: U) -> List where T: Clone, U: RangeBounds, { List::from_vec( self.vec[range.lower_bound(0) as usize..range.upper_bound(self.lens()) as usize] .to_vec(), ) } #[inline] pub fn first_exn(&self) -> &T { self.first().unwrap() } #[inline] pub fn last_exn(&self) -> &T { self.last().unwrap() } #[inline] pub fn pop_exn(&mut self) -> T { self.pop().unwrap() } #[inline] pub fn min_exn(&self) -> &T where T: Ord, { self.min().unwrap() } #[inline] pub fn max_exn(&self) -> &T where T: Ord, { self.max().unwrap() } #[inline] pub fn argmin_exn(&self) -> isize where T: Ord, { self.argmin().unwrap() } #[inline] pub fn argmax_exn(&self) -> isize where T: Ord, { self.argmax().unwrap() } #[inline] pub fn find_exn

(&self, predicate: P) -> &T where P: FnMut(&T) -> bool, { self.find(predicate).unwrap() } #[inline] pub fn index_of_exn

(&self, predicate: P) -> isize where P: FnMut(&T) -> bool, { self.index_of(predicate).unwrap() } } impl std::ops::BitXorAssign for List { #[inline] fn bitxor_assign(&mut self, rhs: T) { self.push(rhs); } } impl Index for List { type Output = T; #[inline] fn index(&self, index: isize) -> &Self::Output { if cfg!(debug_assertions) { self.vec.index(index as usize) } else { unsafe { self.vec.get_unchecked(index as usize) } } } } impl IndexMut for List { #[inline] fn index_mut(&mut self, index: isize) -> &mut Self::Output { if cfg!(debug_assertions) { self.vec.index_mut(index as usize) } else { unsafe { self.vec.get_unchecked_mut(index as usize) } } } } impl FromIterator for List { fn from_iter>(iter: U) -> Self { List { vec: iter.into_iter().collect(), } } } impl IntoIterator for List { type Item = T; type IntoIter = std::vec::IntoIter; fn into_iter(self) -> std::vec::IntoIter { self.vec.into_iter() } } impl<'a, T> IntoIterator for &'a List { type Item = &'a T; type IntoIter = Iter<'a, T>; fn into_iter(self) -> Iter<'a, T> { self.vec.iter() } } impl std::fmt::Display for List { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!( f, "{}", self.iter() .map(|x| format!("{}", x)) .collect::>() .join(" ") ) } } impl std::fmt::Debug for List { fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { write!( f, "[{}]", self.iter() .map(|x| format!("{:?}", x)) .collect::>() .join(", ") ) } } impl From> for List { fn from(vec: Vec) -> Self { Self::from_vec(vec) } } impl From<&[T]> for List { fn from(slice: &[T]) -> Self { slice.iter().cloned().collect() } } #[macro_export] macro_rules ! list { () => { $ crate :: arraylist :: List :: new () } ; ($ ($ v : expr) ,+ $ (,) ?) => { $ crate :: arraylist :: List :: from_vec ([$ ($ v) ,+] . to_vec ()) } ; ($ v : expr ; $ a : expr) => { $ crate :: arraylist :: List :: init ($ v , $ a) } ; ($ v : expr ; $ a : expr ; $ ($ rest : expr) ;+) => { $ crate :: arraylist :: List :: init (list ! ($ v ; $ ($ rest) ;+) , $ a) } ; } } pub mod independent { pub mod integer { use std::fmt::Display; pub trait Int: std::ops::Add + std::ops::Sub + std::ops::Mul + std::ops::Div + std::ops::Rem + std::ops::AddAssign + std::ops::SubAssign + std::ops::MulAssign + std::ops::DivAssign + std::hash::Hash + PartialEq + Eq + PartialOrd + Ord + Copy + Display { fn to_u8(&self) -> u8; fn to_u16(&self) -> u16; fn to_u32(&self) -> u32; fn to_u64(&self) -> u64; fn to_u128(&self) -> u128; fn to_i8(&self) -> i8; fn to_i16(&self) -> i16; fn to_i32(&self) -> i32; fn to_i64(&self) -> i64; fn to_i128(&self) -> i128; fn to_usize(&self) -> usize; fn to_isize(&self) -> isize; fn from_u8(x: u8) -> Self; fn from_u16(x: u16) -> Self; fn from_u32(x: u32) -> Self; fn from_u64(x: u64) -> Self; fn from_u128(x: u128) -> Self; fn from_i8(x: i8) -> Self; fn from_i16(x: i16) -> Self; fn from_i32(x: i32) -> Self; fn from_i64(x: i64) -> Self; fn from_i128(x: i128) -> Self; fn from_usize(x: usize) -> Self; fn from_isize(x: isize) -> Self; fn zero() -> Self; fn one() -> Self; fn next(&self) -> Self { *self + Self::one() } } macro_rules ! impl_integer_functions { ($ selftpe : ident , $ ($ tofn : ident , $ fromfn : ident , $ tpe : ident) ,*) => { $ (fn $ tofn (& self) -> $ tpe { * self as $ tpe } fn $ fromfn (x : $ tpe) -> Self { x as $ selftpe }) * } ; } macro_rules ! impl_integer { ($ ($ tpe : ident) ,*) => { $ (impl Int for $ tpe { impl_integer_functions ! ($ tpe , to_u8 , from_u8 , u8 , to_u16 , from_u16 , u16 , to_u32 , from_u32 , u32 , to_u64 , from_u64 , u64 , to_u128 , from_u128 , u128 , to_i8 , from_i8 , i8 , to_i16 , from_i16 , i16 , to_i32 , from_i32 , i32 , to_i64 , from_i64 , i64 , to_i128 , from_i128 , i128 , to_usize , from_usize , usize , to_isize , from_isize , isize) ; fn zero () -> Self { 0 } fn one () -> Self { 1 } }) * } ; } impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize); } } pub mod modulo { use crate::independent::integer::Int; use std::marker::PhantomData; use std::ops::*; #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] pub struct ModInt(pub i64, PhantomData<*const T>); impl ModInt { pub fn new(a: U) -> ModInt { let x = a.to_i64(); if x < 0 { ModInt::raw(x % T::M + T::M) } else if x < T::M { ModInt::raw(x) } else { ModInt::raw(x % T::M) } } pub fn pow(self, x: U) -> Self { let mut n = x.to_i64(); let mut a = self; let mut res = Self::raw(1); while n > 0 { if n & 1 == 1 { res *= a; } a = a * a; n >>= 1; } res } pub fn inv(self) -> Self { self.pow(T::M - 2) } #[inline] fn raw(x: i64) -> ModInt { ModInt(x, PhantomData) } } pub trait ConstValue: PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord { const M: i64; } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.0) } } macro_rules ! impl_from_for_modint { ($ ($ tpe : ident) ,*) => { $ (impl < T : ConstValue > From <$ tpe > for ModInt < T > { fn from (n : $ tpe) -> Self { Self :: new (n) } }) * } ; } impl_from_for_modint!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize); impl Add for ModInt { type Output = ModInt; fn add(self, other: ModInt) -> ModInt { let mut ret = self.0 + other.0; if ret >= T::M { ret -= T::M; } Self::raw(ret) } } impl Sub for ModInt { type Output = ModInt; fn sub(self, other: ModInt) -> ModInt { let mut ret = self.0 + T::M - other.0; if ret >= T::M { ret -= T::M } Self::raw(ret) } } impl Mul for ModInt { type Output = ModInt; fn mul(self, other: ModInt) -> ModInt { Self::raw(self.0 * other.0 % T::M) } } impl Div for ModInt { type Output = ModInt; fn div(self, other: ModInt) -> ModInt { self * other.inv() } } impl Rem for ModInt { type Output = ModInt; fn rem(self, other: ModInt) -> ModInt { Self::raw(self.0 % other.0) } } macro_rules! impl_assign { ($ t : ty , $ f : ident , $ f2 : ident) => { impl $t for ModInt { fn $f(&mut self, other: Self) { *self = self.$f2(other); } } }; } impl_assign!(AddAssign, add_assign, add); impl_assign!(SubAssign, sub_assign, sub); impl_assign!(MulAssign, mul_assign, mul); impl_assign!(DivAssign, div_assign, div); impl_assign!(RemAssign, rem_assign, rem); #[macro_export] macro_rules! modint { () => { modint!(1000000007); }; ($ m : expr) => { #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)] pub enum __M {} impl $crate::modulo::ConstValue for __M { const M: i64 = $m; } #[allow(dead_code)] type Z = $crate::modulo::ModInt<__M>; }; } macro_rules ! impl_integer_functions { ($ ($ tofn : ident , $ fromfn : ident , $ tpe : ident) ,*) => { $ (fn $ tofn (& self) -> $ tpe { self . 0 as $ tpe } fn $ fromfn (x : $ tpe) -> Self { Self :: new (x) }) * } ; } impl Int for ModInt { impl_integer_functions!( to_u8, from_u8, u8, to_u16, from_u16, u16, to_u32, from_u32, u32, to_u64, from_u64, u64, to_u128, from_u128, u128, to_i8, from_i8, i8, to_i16, from_i16, i16, to_i32, from_i32, i32, to_i64, from_i64, i64, to_i128, from_i128, i128, to_usize, from_usize, usize, to_isize, from_isize, isize ); fn zero() -> Self { Self::new(0) } fn one() -> Self { Self::new(1) } } } pub mod scanner { use crate::arraylist::List; use std::io::{stdin, BufReader, Bytes, Read, Stdin}; use std::str::FromStr; pub struct Scanner { buf: Bytes>, } impl Scanner { pub fn new() -> Scanner { Scanner { buf: BufReader::new(stdin()).bytes(), } } pub fn read_next(&mut self) -> Option { let token = self .buf .by_ref() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::(); token.parse::().ok() } pub fn read(&mut self) -> T { self.read_next().unwrap() } pub fn readn(&mut self, n: isize) -> List { (0..n).map(|_| self.read::()).collect() } pub fn chars(&mut self) -> List { self.read::().chars().collect() } } }