Known-Well Palindrome Date-Hard Version
题号:NC212624
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 64 M,其他语言128 M
64bit IO Format: %lld

题目描述

This problem is almost the same as the previous one, but has different requirement and constraints.

As time flies by, the composition of our society is always changing. Where the post-1980s and post-1990s generations were almost considered as the era of the past, the reverse is true for the post-1995 and post-2000s generations: the rising of new generations is bound to bring more surprises.

In this year, the brand new post-2020s generation was recently created. On 2nd Feb 2020, it was reported by People's Daily that babies who were born in Changyi District, Jilin City, Jilin Province on this day, would receive a unique identification number only made up of digit '2' and '0'. That is mainly because the date "20200202" is a Palindrome Date.


Nowadays, Little Gyro considers that this kind of phenomenon of Palindrome Date is quite well-known among all the people and decides to play with it. Moreover, Little Gyro made the following new regulations on it:
  • The Palindrome Date should be a valid date, according to the rules of Gregorian calendar(公历历法). Furthermore, it should satisfy the format of "YYYYMMDD", where YYYY, MM and DD represent the year, month and day, respectively.
  • The Palindrome Date should conform the format of "ABCDDCBA", where A, B, C and D represent the digit number at the range of '0' to '9'. Furthermore, it is allowed to be duplicated among each of them.

Now given a series of identification number periods, Little Gyro wants to calculate the number of times if and only if a Palindrome Date (not always consecutive) appears from these given number periods within the specific given order. Please help him.

To simplify this problem, Little Gyro just needs to consider all the circumstances in the 21st century. Please note that all the Palindrome Date should at the range of 1st Jan 2000 and 31st Dec 2099 (both inclusive).

输入描述:

There are multiple test cases. Each case consists a string in one line, indicating several identification number periods, and every two of them is separated by a space.

The length of the string in each line will not exceed . And in one line only containing the single character '#' terminates the input and this test case is not to be processed.

It's guaranteed that the string can only be made up by number digits '0'-'9' and spaces, and the sum of the length of the string of all test cases will not exceed 2×.

输出描述:

For each test case output one integer in one line, indicating the number of times when a Palindrome Date appears.

Because the number may be very large, just output the number mod .
示例1

输入

复制
130402202002021234
320124202332021862
110110116711302020 020208196711301866
022002202002025678
220202202002022021 120202202002022020
#

输出

复制
4
0
1
32
126534

说明

For the first sample, Little Gyro can find 4 Palindrome Dates in total. All of them are "20200202", but composed by different indexes. All the composition is shown as the following index boxes:
· [6,8,9,10,11,12,13,14]
· [7,8,9,10,11,12,13,14]
· [6,8,9,10,11,12,13,16]
· [7,8,9,10,11,12,13,16]

For the second sample, Little Gyro cannot find any Palindrome Dates as well.

For the third sample, Little Gyro can find 1 Palindrome Dates "20200202", composed by the last four digits in the first number period and the first four digits in the second number period. Although there also contains a Palindrome Date "11011011", it is not a valid date in the given interval.