Problem Statement

Takahashi has an unbiased six-sided die and a positive integer R less than 10^9.
Each time the die is cast, it shows one of the numbers 1,2,3,4,5,6 with equal probability, independently of the outcomes of the other trials.
Takahashi will perform the following procedure.
Initially, C=0.

• Cast the die and increment C by 1.
• Let X be the sum of the numbers shown so far. If X-R is a multiple of 10^9, quit the procedure.
• Go back to step 1.

Find the expected value of C at the end of the procedure, modulo 998244353.

Input

The input is given from Standard Input in the following format:
R

Output

Print a single line containing the answer.

Constraints

• $0\lt R\lt10^9$
• R is an integer.

Sample Input 1

1

Sample Output 1

291034221

The expected value of C at the end of the procedure is approximately 833333333.619047619, and 291034221 when represented modulo 998244353.

Sample Input 2

720357616

Sample Output 2

153778832

见题面 Input 部分

见题面 Output 部分