Consider digits strings with length n, how many different strings have the sum of digits are multiple of 4?
There are several test cases end with EOF. For each test case, there is an integer in one line: n, the length of the digits string. (1≤n≤1,000,000,000).
For each case, output the number of digits strings with length n have the sum of digits are multiple of 4 in one line. The numbers maybe very large, you should output the result modular 2019.