#B3883. [信息与未来 2015] 求回文数(加强版)

[信息与未来 2015] 求回文数(加强版)

题目描述

一个正整数,正读和反读都相同的数为回文数,例如 22,131,2442,37073,6,22,131,2442,37073,6,\cdots。所有的 11 位数都是回文数。

现给出一个正整数 nn,求出 [1,n][1,n] 中的回文数的个数。

输入格式

一个整数 nn

输出格式

一个整数,即 1n1\sim n 中全部回文数的个数,答案对 2009111920091119 取模。

24
11

提示

样例解释

112424 中,回文数有 19,11,221\sim 9,11,22,共 1111 个。

数据范围

1n101001\le n\le10^{100}