/// source code (in typescript)

// // @kariay1975/atcoder-tslib is a private package: 
// import {
//   AndDfa,
//   Dfa,
//   Input,
//   InputStdin,
//   LeDfa,
//   Mod,
//   MonoidModSum,
//   Output,
//   dfaDp,
//   int,
//   isControlTag,
//   makeMonoid2,
//   modint,
//   withLog,
// } from '@kariya1975/atcoder-tslib';
// import { GeDfa } from '@kariya1975/atcoder-tslib/lib/dfa_dp';
// // use babel-plugin-macros for speed.
// import {
//   arrayWith,
//   enumerate,
//   range,
// } from '@kariya1975/atcoder-tslib/macro';
// 
// 
// const naive = () => {
// 
// };
// 
// const mod = new Mod(998244353);
// 
// type State = {
//   inLeading0: boolean,
//   len: int,
//   count: int[],
// };
// 
// class GoodNumberDfa extends Dfa<int, State> {
//   constructor(
//     // public n: int,
//   ) {
//     super();
//   }
//   get initialState(): State {
//     return {
//       inLeading0: true,
//       len: 0,
//       count: arrayWith(10, () => 0),
//     };
//   }
//   nextState(s: State, c: int): State {
//     if (s.inLeading0 && c == 0) {
//       return {
//         ...s,
//         // len: s.len + 1,
//       };
//     }
//     return {
//       inLeading0: false,
//       len: s.len + 1,
//       count: arrayWith(10, i => i === c ? (s.count[i] + 1) % 2 : s.count[i]),
//     };
//   }
//   isAcceptedState(s: State): boolean {
//     return /*s.len === this.n &&*/ !s.inLeading0 && s.count.every(x => x === 0);
//   }
//   toStringState(s: State): string {
//     return `${s.len}:${s.count.join('')}`;
//   }
// }
// 
// const solve = (N: string): modint => {
//   const result = dfaDp(
//     new AndDfa(
//       new LeDfa(N.split('').map(x => Number(x))),
//       new GoodNumberDfa(),
//     ),
//     arrayWith(10, i => i),
//     N.length,
//     (m, c, s) => {
//     //   return makeMonoid2(
//     //     new MonoidModSum(
//     //       mod.add(
//     //         mod.mult(mod.fromInt(10), m.value[0]), 
//     //         mod.mult(mod.fromInt(c), m.value[1]),
//     //       ), 
//     //       mod,
//     //     ),
//     //     new MonoidModSum(m.value[1], mod)
//     //   );
//       // const n = m.op(new MonoidModSum(mod.fromInt(1), mod));
// // console.error(m.value, c, s?.len, s?.count.join(''), n.value);
//       return m;
//     },
//     // makeMonoid2(new MonoidModSum(mod.fromInt(0), mod), new MonoidModSum(mod.fromInt(1), mod)),
//     new MonoidModSum(mod.fromInt(1), mod),
//   );
// // console.error(result.value[0], result.value[1])
//   // return result.value[1];
//   return result.value;
// };
// 
// // let m = new MonoidModSum(0 as modint, mod);
// // m = m.op(new MonoidModSum(1 as modint, mod)) as any;
// // m = m.op(new MonoidModSum(1 as modint, mod)) as any;
// // m = m.op(new MonoidModSum(1 as modint, mod)) as any;
// // console.error(m.value)
// // process.exit(0)
// 
// // let result = 0;
// // for (const i of range(37181 + 1)) {
// //   const s = i.toString().padStart(5, '0');
// // // console.error(s)
// //   // const d = new GoodNumberDfa();
// //   const d = 
// //     // new AndDfa(
// //       // new LeDfa('198'.split('').map(x => Number(x)))
// //       new GoodNumberDfa()
// //     // )
// //   ;
// //   let t = d.initialState;
// //   for (const c of s) {
// //     t = d.nextState(t, Number(c));
// //     if (t === null) break;
// //   }
// //   if (t !== null && d.isAcceptedState(t)) {
// //     // console.error(i);
// //     result += 1;
// //   } else {
// //     // console.error(i)
// //   }
// // }
// // console.error(result)
// // process.exit(0)
// 
// // const d = new GoodNumberDfa();
// // let s = d.initialState;
// // s = d.nextState(s, 2)
// // console.error(d.isAcceptedState(s))
// // s = d.nextState(s, 2)
// // console.error(d.isAcceptedState(s))
// // s = d.nextState(s, 1)
// // console.error(d.isAcceptedState(s))
// // s = d.nextState(s, 1)
// // console.error(d.isAcceptedState(s))
// // process.exit(0)
// 
// const main = (input: Input, output: Output): void => {
//   const N = input.getString();
//   const result = solve(N);
//   output.push(result);
// };
// 
// const input = new InputStdin();
// input.setup().then(_ => {
//   const output = new Output();
//   try {
//     main(input, output);
//     output.print();
//   } catch (e) {
//     if (isControlTag(e, 'earlyExit')) {
//       output.print();
//     } else {
//       throw e;
//     }
//   }
// }).catch(e => {
//   console.error(e);
// });

// /// The code above transpiles as follows:
var mt=Object.create;var G=Object.defineProperty;var gt=Object.getOwnPropertyDescriptor;var yt=Object.getOwnPropertyNames;var vt=Object.getPrototypeOf,_t=Object.prototype.hasOwnProperty;var L=(i,t)=>()=>(t||i((t={exports:{}}).exports,t),t.exports);var wt=(i,t,e,r)=>{if(t&&typeof t=="object"||typeof t=="function")for(let n of yt(t))!_t.call(i,n)&&n!==e&&G(i,n,{get:()=>t[n],enumerable:!(r=gt(t,n))||r.enumerable});return i};var $=(i,t,e)=>(e=i!=null?mt(vt(i)):{},wt(t||!i||!i.__esModule?G(e,"default",{value:i,enumerable:!0}):e,i));var U=L((Jt,Q)=>{"use strict";var xt=function(i,t){return i<t};function m(i){if(!(this instanceof m))return new m(i);this.array=[],this.size=0,this.compare=i||xt}m.prototype.clone=function(){var i=new m(this.compare);return i.size=this.size,i.array=this.array.slice(0,this.size),i};m.prototype.add=function(i){var t=this.size;this.array[this.size]=i,this.size+=1;for(var e,r;t>0&&(e=t-1>>1,r=this.array[e],!!this.compare(i,r));)this.array[t]=r,t=e;this.array[t]=i};m.prototype.heapify=function(i){this.array=i,this.size=i.length;var t;for(t=this.size>>1;t>=0;t--)this._percolateDown(t)};m.prototype._percolateUp=function(i,t){for(var e=this.array[i],r,n;i>0&&(r=i-1>>1,n=this.array[r],!(!t&&!this.compare(e,n)));)this.array[i]=n,i=r;this.array[i]=e};m.prototype._percolateDown=function(i){for(var t=this.size,e=this.size>>>1,r=this.array[i],n,s,o;i<e&&(n=(i<<1)+1,s=n+1,o=this.array[n],s<t&&this.compare(this.array[s],o)&&(n=s,o=this.array[s]),!!this.compare(o,r));)this.array[i]=o,i=n;this.array[i]=r};m.prototype._removeAt=function(i){if(!(i>this.size-1||i<0))return this._percolateUp(i,!0),this.poll()};m.prototype.remove=function(i){for(var t=0;t<this.size;t++)if(!this.compare(this.array[t],i)&&!this.compare(i,this.array[t]))return this._removeAt(t),!0;return!1};m.prototype.removeOne=function(i){if(typeof i=="function"){for(var t=0;t<this.size;t++)if(i(this.array[t]))return this._removeAt(t)}};m.prototype.removeMany=function(i,t){if(typeof i!="function"||this.size<1)return[];t=t?Math.min(t,this.size):this.size;for(var e=0,r=new Array(t),n=0,s=new Array(this.size);e<t&&!this.isEmpty();){var o=this.poll();i(o)?r[e++]=o:s[n++]=o}r.length=e;for(var h=0;h<n;)this.add(s[h++]);return r};m.prototype.peek=function(){if(this.size!=0)return this.array[0]};m.prototype.poll=function(){if(this.size!=0){var i=this.array[0];return this.size>1?(this.array[0]=this.array[--this.size],this._percolateDown(0)):this.size-=1,i}};m.prototype.replaceTop=function(i){if(this.size!=0){var t=this.array[0];return this.array[0]=i,this._percolateDown(0),t}};m.prototype.trim=function(){this.array=this.array.slice(0,this.size)};m.prototype.isEmpty=function(){return this.size===0};m.prototype.forEach=function(i){if(!(this.isEmpty()||typeof i!="function"))for(var t=0,e=this.clone();!e.isEmpty();)i(e.poll(),t++)};m.prototype.kSmallest=function(i){if(this.size==0)return[];i=Math.min(this.size,i);var t=new m(this.compare);let e=Math.min((i>0?Math.pow(2,i-1):0)+1,this.size);t.size=e,t.array=this.array.slice(0,e);for(var r=new Array(i),n=0;n<i;n++)r[n]=t.poll();return r};Q.exports=m});var et=L((ce,tt)=>{"use strict";function c(i){if(this._capacity=Z(i),this._length=0,this._front=0,J(i)){for(var t=i.length,e=0;e<t;++e)this[e]=i[e];this._length=t}}c.prototype.toArray=function(){for(var t=this._length,e=new Array(t),r=this._front,n=this._capacity,s=0;s<t;++s)e[s]=this[r+s&n-1];return e};c.prototype.push=function(t){var e=arguments.length,r=this._length;if(e>1){var n=this._capacity;if(r+e>n){for(var o=0;o<e;++o){this._checkCapacity(r+1);var s=this._front+r&this._capacity-1;this[s]=arguments[o],r++,this._length=r}return r}else{for(var s=this._front,o=0;o<e;++o)this[s+r&n-1]=arguments[o],s++;return this._length=r+e,r+e}}if(e===0)return r;this._checkCapacity(r+1);var o=this._front+r&this._capacity-1;return this[o]=t,this._length=r+1,r+1};c.prototype.pop=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1,r=this[e];return this[e]=void 0,this._length=t-1,r}};c.prototype.shift=function(){var t=this._length;if(t!==0){var e=this._front,r=this[e];return this[e]=void 0,this._front=e+1&this._capacity-1,this._length=t-1,r}};c.prototype.unshift=function(t){var e=this._length,r=arguments.length;if(r>1){var o=this._capacity;if(e+r>o){for(var h=r-1;h>=0;h--){this._checkCapacity(e+1);var o=this._capacity,n=(this._front-1&o-1^o)-o;this[n]=arguments[h],e++,this._length=e,this._front=n}return e}else{for(var s=this._front,h=r-1;h>=0;h--){var n=(s-1&o-1^o)-o;this[n]=arguments[h],s=n}return this._front=s,this._length=e+r,e+r}}if(r===0)return e;this._checkCapacity(e+1);var o=this._capacity,h=(this._front-1&o-1^o)-o;return this[h]=t,this._length=e+1,this._front=h,e+1};c.prototype.peekBack=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1;return this[e]}};c.prototype.peekFront=function(){if(this._length!==0)return this[this._front]};c.prototype.get=function(t){var e=t;if(e===(e|0)){var r=this._length;if(e<0&&(e=e+r),!(e<0||e>=r))return this[this._front+e&this._capacity-1]}};c.prototype.isEmpty=function(){return this._length===0};c.prototype.clear=function(){for(var t=this._length,e=this._front,r=this._capacity,n=0;n<t;++n)this[e+n&r-1]=void 0;this._length=0,this._front=0};c.prototype.toString=function(){return this.toArray().toString()};c.prototype.valueOf=c.prototype.toString;c.prototype.removeFront=c.prototype.shift;c.prototype.removeBack=c.prototype.pop;c.prototype.insertFront=c.prototype.unshift;c.prototype.insertBack=c.prototype.push;c.prototype.enqueue=c.prototype.push;c.prototype.dequeue=c.prototype.shift;c.prototype.toJSON=c.prototype.toArray;Object.defineProperty(c.prototype,"length",{get:function(){return this._length},set:function(){throw new RangeError("")}});c.prototype._checkCapacity=function(t){this._capacity<t&&this._resizeTo(Z(this._capacity*1.5+16))};c.prototype._resizeTo=function(t){var e=this._capacity;this._capacity=t;var r=this._front,n=this._length;if(r+n>e){var s=r+n&e-1;At(this,0,this,e,s)}};var J=Array.isArray;function At(i,t,e,r,n){for(var s=0;s<n;++s)e[s+r]=i[s+t],i[s+t]=void 0}function Nt(i){return i=i>>>0,i=i-1,i=i|i>>1,i=i|i>>2,i=i|i>>4,i=i|i>>8,i=i|i>>16,i+1}function Z(i){if(typeof i!="number")if(J(i))i=i.length;else return 16;return Nt(Math.min(Math.max(16,i),1073741824))}tt.exports=c});var ht=L((Ke,ot)=>{"use strict";ot.exports=$t;var f=0,a=1;function _(i,t,e,r,n,s){this._color=i,this.key=t,this.value=e,this.left=r,this.right=n,this._count=s}function z(i){return new _(i._color,i.key,i.value,i.left,i.right,i._count)}function I(i,t){return new _(i,t.key,t.value,t.left,t.right,t._count)}function p(i){i._count=1+(i.left?i.left._count:0)+(i.right?i.right._count:0)}function S(i,t){this._compare=i,this.root=t}var v=S.prototype;Object.defineProperty(v,"keys",{get:function(){var i=[];return this.forEach(function(t,e){i.push(t)}),i}});Object.defineProperty(v,"values",{get:function(){var i=[];return this.forEach(function(t,e){i.push(e)}),i}});Object.defineProperty(v,"length",{get:function(){return this.root?this.root._count:0}});v.insert=function(i,t){for(var e=this._compare,r=this.root,n=[],s=[];r;){var o=e(i,r.key);n.push(r),s.push(o),o<=0?r=r.left:r=r.right}n.push(new _(f,i,t,null,null,1));for(var h=n.length-2;h>=0;--h){var r=n[h];s[h]<=0?n[h]=new _(r._color,r.key,r.value,n[h+1],r.right,r._count+1):n[h]=new _(r._color,r.key,r.value,r.left,n[h+1],r._count+1)}for(var h=n.length-1;h>1;--h){var u=n[h-1],r=n[h];if(u._color===a||r._color===a)break;var l=n[h-2];if(l.left===u)if(u.left===r){var y=l.right;if(y&&y._color===f)u._color=a,l.right=I(a,y),l._color=f,h-=1;else{if(l._color=f,l.left=u.right,u._color=a,u.right=l,n[h-2]=u,n[h-1]=r,p(l),p(u),h>=3){var g=n[h-3];g.left===l?g.left=u:g.right=u}break}}else{var y=l.right;if(y&&y._color===f)u._color=a,l.right=I(a,y),l._color=f,h-=1;else{if(u.right=r.left,l._color=f,l.left=r.right,r._color=a,r.left=u,r.right=l,n[h-2]=r,n[h-1]=u,p(l),p(u),p(r),h>=3){var g=n[h-3];g.left===l?g.left=r:g.right=r}break}}else if(u.right===r){var y=l.left;if(y&&y._color===f)u._color=a,l.left=I(a,y),l._color=f,h-=1;else{if(l._color=f,l.right=u.left,u._color=a,u.left=l,n[h-2]=u,n[h-1]=r,p(l),p(u),h>=3){var g=n[h-3];g.right===l?g.right=u:g.left=u}break}}else{var y=l.left;if(y&&y._color===f)u._color=a,l.left=I(a,y),l._color=f,h-=1;else{if(u.left=r.right,l._color=f,l.right=r.left,r._color=a,r.right=u,r.left=l,n[h-2]=r,n[h-1]=u,p(l),p(u),p(r),h>=3){var g=n[h-3];g.right===l?g.right=r:g.left=r}break}}}return n[0]._color=a,new S(e,n[0])};var Dt=W(function i(t,e){if(e.left){var r=i(t,e.left);if(r)return r}var r=t(e.key,e.value);if(r)return r;if(e.right)return()=>i(t,e.right)}),Ot=W(function i(t,e,r,n){var s=e(t,n.key);if(s<=0){if(n.left){var o=i(t,e,r,n.left);if(o)return o}var o=r(n.key,n.value);if(o)return o}if(n.right)return()=>i(t,e,r,n.right)}),Bt=W(function i(t,e,r,n,s){var o=r(t,s.key),h=r(e,s.key),u;if(o<=0&&(s.left&&(u=i(t,e,r,n,s.left),u)||h>0&&(u=n(s.key,s.value),u)))return u;if(h>0&&s.right)return()=>i(t,e,r,n,s.right)});v.forEach=function(t,e,r){if(this.root)switch(arguments.length){case 1:return Dt(t,this.root);case 2:return Ot(e,this._compare,t,this.root);case 3:return this._compare(e,r)>=0?void 0:Bt(e,r,this._compare,t,this.root)}};Object.defineProperty(v,"begin",{get:function(){for(var i=[],t=this.root;t;)i.push(t),t=t.left;return new w(this,i)}});Object.defineProperty(v,"end",{get:function(){for(var i=[],t=this.root;t;)i.push(t),t=t.right;return new w(this,i)}});v.at=function(i){if(i<0)return new w(this,[]);for(var t=this.root,e=[];;){if(e.push(t),t.left){if(i<t.left._count){t=t.left;continue}i-=t.left._count}if(!i)return new w(this,e);if(i-=1,t.right){if(i>=t.right._count)break;t=t.right}else break}return new w(this,[])};v.ge=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s<=0&&(n=r.length),s<=0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.gt=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s<0&&(n=r.length),s<0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.lt=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s>0&&(n=r.length),s<=0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.le=function(i){for(var t=this._compare,e=this.root,r=[],n=0;e;){var s=t(i,e.key);r.push(e),s>=0&&(n=r.length),s<0?e=e.left:e=e.right}return r.length=n,new w(this,r)};v.find=function(i){for(var t=this._compare,e=this.root,r=[];e;){var n=t(i,e.key);if(r.push(e),n===0)return new w(this,r);n<=0?e=e.left:e=e.right}return new w(this,[])};v.remove=function(i){var t=this.find(i);return t?t.remove():this};v.get=function(i){for(var t=this._compare,e=this.root;e;){var r=t(i,e.key);if(r===0)return e.value;r<=0?e=e.left:e=e.right}};function w(i,t){this.tree=i,this._stack=t}var x=w.prototype;Object.defineProperty(x,"valid",{get:function(){return this._stack.length>0}});Object.defineProperty(x,"node",{get:function(){return this._stack.length>0?this._stack[this._stack.length-1]:null},enumerable:!0});x.clone=function(){return new w(this.tree,this._stack.slice())};function st(i,t){i.key=t.key,i.value=t.value,i.left=t.left,i.right=t.right,i._color=t._color,i._count=t._count}function Ct(i){for(var t,e,r,n,s=i.length-1;s>=0;--s){if(t=i[s],s===0){t._color=a;return}if(e=i[s-1],e.left===t){if(r=e.right,r.right&&r.right._color===f){if(r=e.right=z(r),n=r.right=z(r.right),e.right=r.left,r.left=e,r.right=n,r._color=e._color,t._color=a,e._color=a,n._color=a,p(e),p(r),s>1){var o=i[s-2];o.left===e?o.left=r:o.right=r}i[s-1]=r;return}else if(r.left&&r.left._color===f){if(r=e.right=z(r),n=r.left=z(r.left),e.right=n.left,r.left=n.right,n.left=e,n.right=r,n._color=e._color,e._color=a,r._color=a,t._color=a,p(e),p(r),p(n),s>1){var o=i[s-2];o.left===e?o.left=n:o.right=n}i[s-1]=n;return}if(r._color===a)if(e._color===f){e._color=a,e.right=I(f,r);return}else{e.right=I(f,r);continue}else{if(r=z(r),e.right=r.left,r.left=e,r._color=e._color,e._color=f,p(e),p(r),s>1){var o=i[s-2];o.left===e?o.left=r:o.right=r}i[s-1]=r,i[s]=e,s+1<i.length?i[s+1]=t:i.push(t),s=s+2}}else{if(r=e.left,r.left&&r.left._color===f){if(r=e.left=z(r),n=r.left=z(r.left),e.left=r.right,r.right=e,r.left=n,r._color=e._color,t._color=a,e._color=a,n._color=a,p(e),p(r),s>1){var o=i[s-2];o.right===e?o.right=r:o.left=r}i[s-1]=r;return}else if(r.right&&r.right._color===f){if(r=e.left=z(r),n=r.right=z(r.right),e.left=n.right,r.right=n.left,n.right=e,n.left=r,n._color=e._color,e._color=a,r._color=a,t._color=a,p(e),p(r),p(n),s>1){var o=i[s-2];o.right===e?o.right=n:o.left=n}i[s-1]=n;return}if(r._color===a)if(e._color===f){e._color=a,e.left=I(f,r);return}else{e.left=I(f,r);continue}else{if(r=z(r),e.left=r.right,r.right=e,r._color=e._color,e._color=f,p(e),p(r),s>1){var o=i[s-2];o.right===e?o.right=r:o.left=r}i[s-1]=r,i[s]=e,s+1<i.length?i[s+1]=t:i.push(t),s=s+2}}}}x.remove=function(){var i=this._stack;if(i.length===0)return this.tree;var t=new Array(i.length),e=i[i.length-1];t[t.length-1]=new _(e._color,e.key,e.value,e.left,e.right,e._count);for(var r=i.length-2;r>=0;--r){var e=i[r];e.left===i[r+1]?t[r]=new _(e._color,e.key,e.value,t[r+1],e.right,e._count):t[r]=new _(e._color,e.key,e.value,e.left,t[r+1],e._count)}if(e=t[t.length-1],e.left&&e.right){var n=t.length;for(e=e.left;e.right;)t.push(e),e=e.right;var s=t[n-1];t.push(new _(e._color,s.key,s.value,e.left,e.right,e._count)),t[n-1].key=e.key,t[n-1].value=e.value;for(var r=t.length-2;r>=n;--r)e=t[r],t[r]=new _(e._color,e.key,e.value,e.left,t[r+1],e._count);t[n-1].left=t[n]}if(e=t[t.length-1],e._color===f){var o=t[t.length-2];o.left===e?o.left=null:o.right===e&&(o.right=null),t.pop();for(var r=0;r<t.length;++r)t[r]._count--;return new S(this.tree._compare,t[0])}else if(e.left||e.right){e.left?st(e,e.left):e.right&&st(e,e.right),e._color=a;for(var r=0;r<t.length-1;++r)t[r]._count--;return new S(this.tree._compare,t[0])}else{if(t.length===1)return new S(this.tree._compare,null);for(var r=0;r<t.length;++r)t[r]._count--;var h=t[t.length-2];Ct(t),h.left===e?h.left=null:h.right=null}return new S(this.tree._compare,t[0])};Object.defineProperty(x,"key",{get:function(){if(this._stack.length>0)return this._stack[this._stack.length-1].key},enumerable:!0});Object.defineProperty(x,"value",{get:function(){if(this._stack.length>0)return this._stack[this._stack.length-1].value},enumerable:!0});Object.defineProperty(x,"index",{get:function(){var i=0,t=this._stack;if(t.length===0){var e=this.tree.root;return e?e._count:0}else t[t.length-1].left&&(i=t[t.length-1].left._count);for(var r=t.length-2;r>=0;--r)t[r+1]===t[r].right&&(++i,t[r].left&&(i+=t[r].left._count));return i},enumerable:!0});x.next=function(){var i=this._stack;if(i.length!==0){var t=i[i.length-1];if(t.right)for(t=t.right;t;)i.push(t),t=t.left;else for(i.pop();i.length>0&&i[i.length-1].right===t;)t=i[i.length-1],i.pop()}};Object.defineProperty(x,"hasNext",{get:function(){var i=this._stack;if(i.length===0)return!1;if(i[i.length-1].right)return!0;for(var t=i.length-1;t>0;--t)if(i[t-1].left===i[t])return!0;return!1}});x.update=function(i){var t=this._stack;if(t.length===0)throw new Error("Can't update empty node!");var e=new Array(t.length),r=t[t.length-1];e[e.length-1]=new _(r._color,r.key,i,r.left,r.right,r._count);for(var n=t.length-2;n>=0;--n)r=t[n],r.left===t[n+1]?e[n]=new _(r._color,r.key,r.value,e[n+1],r.right,r._count):e[n]=new _(r._color,r.key,r.value,r.left,e[n+1],r._count);return new S(this.tree._compare,e[0])};x.prev=function(){var i=this._stack;if(i.length!==0){var t=i[i.length-1];if(t.left)for(t=t.left;t;)i.push(t),t=t.right;else for(i.pop();i.length>0&&i[i.length-1].left===t;)t=i[i.length-1],i.pop()}};Object.defineProperty(x,"hasPrev",{get:function(){var i=this._stack;if(i.length===0)return!1;if(i[i.length-1].left)return!0;for(var t=i.length-1;t>0;--t)if(i[t-1].right===i[t])return!0;return!1}});function Lt(i,t){return i<t?-1:i>t?1:0}function $t(i){return new S(i||Lt,null)}function W(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}});var A=require("fs"),O=class{constructor(t){this.data=t!=null?t:"",this.index=0}isSpace(t){return t===" "||t===`
`}getString(){for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;let t=this.index;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)this.index++;let e=this.index;return this.data.slice(t,e)}getCharList(){let t=[];for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)t.push(this.data[this.index]),this.index++;return t}getBigInt(){return BigInt(this.getString())}getInt(){return Number(this.getString())}getNumber(){return Number(this.getString())}getNumbers(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getNumber());return e}getBigInts(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getBigInt());return e}getInts(t){let e=Array(t);for(let r=0,n=t;r<n;++r)e[r]=this.getInt();return e}getStrings(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getString());return e}getMatrix(){let[t,e]=this.getInts(2),r=[];for(let n=0,s=t;n<s;++n)r.push(this.getInts(e));return[t,e,r]}getMatrixWithExtraData(t){let[e,r]=this.getInts(2),n=this.getInts(t),s=[];for(let o=0,h=e;o<h;++o)s.push(this.getInts(r));return[e,r,n,s]}getSquareMatrix(){let t=this.getInt(),e=[];for(let r=0,n=t;r<n;++r)e.push(this.getInts(t));return[t,e]}forEach(t){let e=this.getInt();for(let r=0,n=e;r<n;++r)t(r)}case(t){let e=this.getInt();if(!t.has(e))throw new Error(`unknown kind ${e}`);t.get(e)(e)}getSeries(){let t=this.getInt(),e=this.getInts(t);return[t,e]}getSeriesWithExtraData(t){let e=this.getInt(),r=this.getInts(t),n=this.getInts(e);return[[e,...r],n]}getGraphWithAdjList(){let[t,e]=this.getInts(2),r=d(t,()=>[]);for(let n=0,s=e;n<s;++n){let[o,h]=this.getInts(2);r[o-1].push(h-1),r[h-1].push(o-1)}return[t,e,r]}getGraphWithAdjMatrix(){let[t,e]=this.getInts(2),r=d(t,()=>d(t,()=>!1));for(let n=0,s=e;n<s;++n){let[o,h]=this.getInts(2);r[o-1][h-1]=!0,r[h-1][o-1]=!0}return[t,e,r]}getIntPairs(t){let e=[],r=[];for(let n=0,s=t;n<s;++n){let[o,h]=this.getInts(2);e.push(o),r.push(h)}return[e,r]}},N=class extends O{constructor(){super(),(0,A.existsSync)("/dev/stdin")&&(super.data=(0,A.readFileSync)("/dev/stdin","utf-8"))}async setup(){if((0,A.existsSync)("/dev/stdin"))return;let t=[];for await(let n of process.stdin)t.push(n);let r=Buffer.concat(t).toString();super.data=r}};var zt=$(U());var qt=$(et());var d=(i,t)=>{let e=new Array(i);for(let r=0;r<i;++r)e[r]=t(r);return e};var b=class{},P=(i,t,e,r,n)=>{let s=new Map;s.set(i.toStringState(i.initialState),[i.initialState,n]);for(let h=0,u=e;h<u;++h){let l=new Map;for(let[y,[g,pt]]of s.entries())for(let C=0,dt=t.length;C<dt;++C){let H=t[C];{let F=i.nextState(g,H);if(F===null)continue;let Y=r(pt,H,g),D=i.toStringState(F);l.has(D)?l.set(D,[F,l.get(D)[1].op(Y)]):l.set(D,[F,Y])}}s=l}let o=n.id();for(let[h,[u,l]]of s.entries())i.isAcceptedState(u)&&(o=o.op(l));return o};var q=class extends b{constructor(t,e){super(),this.A1=t,this.A2=e}get initialState(){return[this.A1.initialState,this.A2.initialState]}toStringState([t,e]){return`${this.A1.toStringState(t)},${this.A2.toStringState(e)}}`}nextState(t,e){let r=this.A1.nextState(t[0],e);if(r===null)return null;let n=this.A2.nextState(t[1],e);return n===null?null:[r,n]}isAcceptedState(t){return this.A1.isAcceptedState(t[0])&&this.A2.isAcceptedState(t[1])}},E=class extends b{constructor(t){super(),this.n=t}get initialState(){return{i:0,tight:!0}}toStringState(t){return`${t.i},${t.tight?1:0}`}nextState(t,e){return this.n.length>t.i?t.tight?e<this.n[t.i]?{i:t.i+1,tight:!1}:e===this.n[t.i]?{i:t.i+1,tight:!0}:null:{i:t.i+1,tight:!1}:null}isAcceptedState(t){return!0}getStates(){let t=[];for(let e=0,r=this.n.length;e<r;++e)t.push({i:e,tight:!1}),t.push({i:e,tight:!0});return t}};var it=nt((i,t)=>t===0?i:()=>it(t,i%t));var R=nt((i,t)=>t===0n?i:()=>R(t,i%t));function nt(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var Pt=$(ht());var Rt=ut((i,t)=>{if(t.length===0)return i;let[e,...r]=t;return()=>Rt(i[e],r)}),Wt=ut((i,t,e)=>{let[r,...n]=t;if(n.length>0)return()=>Wt(i[r],n,e);i[r]=e});function ut(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var k=class{constructor(t){this.mod=t,this.mod=t,this.invTable=new Map,this.invTable.set(0,0),this.invTable.set(1,1),this.factorialTable=[1],this.factorialInvTable=[1],t<=2**32&&(this.mult=this.mult32)}fromInt(t){return t}fromBigInt(t){return Number(t%BigInt(this.mod))}inv_slow(t){let e=1;for(let r=0,n=this.mod-2;r<n;++r)e=this.mult(e,t);return e}mult(t,e){let r=t*e;return r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number(BigInt(t)*BigInt(e)%BigInt(this.mod))}mult32(t,e){let r=t*e;return r<=Number.MAX_SAFE_INTEGER?this.fromInt(r%this.mod):this.fromInt(((t&4095)*e+(t>>12)*e%this.mod*4096)%this.mod)}inv_slow2(t){let e=this.mod-2,r=t,n=1;for(;e>0;)(e&1)===1&&(n=this.mult(n,r)),r=this.mult(r,r),e=e>>1;return n}inv(t){if(this.invTable.has(t))return this.invTable.get(t);let e=t,r=this.mod-this.mult(Math.floor(this.mod/e),this.inv(this.mod%e));return this.invTable.set(t,r),r}factorial(t){if(this.factorialTable.length<=t)for(let e=this.factorialTable.length;e<t+1;++e)this.factorialTable.push(this.mult(this.factorialTable[e-1],e));return this.factorialTable[t]}factorial_fast(t,e=[0]){if(e[0]=0,t===0)return 1;let r=Math.floor(t/this.mod),n=this.factorial_fast(r,e);return e[0]+=r,r%2!==0?this.mult(n,this.mod-this.factorial(t%this.mod)):this.mult(n,this.factorial(t%this.mod))}factorialInv(t){if(this.factorialInvTable.length<=t)for(let e=this.factorialInvTable.length;e<t+1;++e)this.factorialInvTable.push(this.mult(this.factorialInvTable[e-1],this.inv(e)));return this.factorialInvTable[t]}combination(t,e){let r=this.factorial(t);return r=this.mult(r,this.mult(this.factorialInv(t-e),this.factorialInv(e))),r}add(t,e){let r=t+e;return r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number((BigInt(t)+BigInt(e))%BigInt(this.mod))}sub(t,e){let r=t-e;return r<0&&(r+=this.mod),r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number((BigInt(t)-BigInt(e))%BigInt(this.mod))}divide(t,e){return this.mult(t,this.inv_slow2(e))}normalize(t){return t>=0&&t<this.mod?t:t>=0?t%this.mod:t%this.mod+this.mod}mults(...t){let e=this.fromInt(1);for(let r of t)e=this.mult(e,r);return e}pow(t,e){if(e===0)return 1;if(e%2===0){let n=this.pow(t,e/2);return this.mult(n,n)}let r=this.pow(t,Math.floor(e/2));return this.mult(this.mult(r,r),t)}extGcd(t,e){if(e!==0){let[r,n,s]=this.extGcd(e,this.fromInt(t%e));return r=this.sub(r,this.mult(this.divide(t,e),n)),[n,r,s]}else return[this.fromInt(1),this.fromInt(0),t]}};var B=class{constructor(t,e,r){this.value=t,this.op=e,this.id=r}};var T=class i extends B{constructor(t,e){super(t,r=>new i(e.add(t,r.value),e),()=>new i(e.fromInt(0),e)),this.n=t,this.mod=e}};var M=class{buffer=[];constructor(){}push(t){this.buffer.push(t)}yesNo(t){this.push(t?"Yes":"No")}list(t){this.push(t.join(" "))}lists(t){this.push(t.length);for(let e of t)this.list(e)}listNl(t){for(let e of t)this.push(e)}print(){console.log(this.buffer.join(`
`))}earlyExitTag(){return"earlyExit"}isEarlyExitTag(t){return t==="earlyExit"}};var at=(i,t)=>i===t;var V=at;var ct=new k(998244353),j=class extends b{constructor(){super()}get initialState(){return{inLeading0:!0,len:0,count:new Array(10).fill(0)}}nextState(t,e){return t.inLeading0&&e==0?{...t}:{inLeading0:!1,len:t.len+1,count:d(10,r=>r===e?(t.count[r]+1)%2:t.count[r])}}isAcceptedState(t){return!t.inLeading0&&t.count.every(e=>e===0)}toStringState(t){return`${t.len}:${t.count.join("")}`}},Yt=i=>P(new q(new E(i.split("").map(e=>Number(e))),new j),d(10,e=>e),i.length,(e,r,n)=>e,new T(ct.fromInt(1),ct)).value,Gt=(i,t)=>{let e=i.getString(),r=Yt(e);t.push(r)},ft=new N;ft.setup().then(i=>{let t=new M;try{Gt(ft,t),t.print()}catch(e){if(V(e,"earlyExit"))t.print();else throw e}}).catch(i=>{console.error(i)});