405863: GYM102136 E Sweet motivation

There is nothing the Little Programmer enjoys better than calculation. At the same time, he doesn’t really enjoy reading books, which he must read in Literature classes. Especially if they are thick. Especially if they are very very fat. That’s why he decided to ignore reading a book containing N pages and put up with bad grade. But the literature teacher was not ready to give up, none of his students had escaped acquaintance with this productive writer. To encourage the Little Programmer’s interest, he invented a rule. After every page read, the student gets just as many sweets as the absolute value of differences of the sums of the digits in the numbers of the previous and the next pages. Such a sweet motivation radically changed the situation: the book was read from the first to the last page immediately. Now all that remains is to find out how many sweets the Little Programmer can receive for such a feat. He has already counted, but the teacher needs your help.

The first and only line contains the number of pages in the book. It’s the integer N.

The single line contains the required number of sweets. There are a lot of them, so print it modulo 10⁹ + 7.

29

42