Background

Source: TYCPC 4th, Check: not_clever_syl.

Alice wants to train Bob’s “tree hollow” skills.

Problem Description

Alice says that every day, Bob just needs to fill in a table, which is a $1 \times n$ matrix. In each cell, he can write a number $x(0 \leq x \leq 7)$.

Alice will check this table. If the sum of the numbers in all cells is divisible by $7$, Alice will take Bob to eat Crazy Thursday.

Bob really likes going to eat Crazy Thursday, but to prevent Bob from filling in the same table repeatedly, Alice added a rule that the way of filling it in must be different every day.

Bob wants to know the maximum number of times he can eat Crazy Thursday.

Since Bob thinks this number may be very large, you only need to output this number modulo $101$.

Input Format

Input one integer $n$.

Output Format

One line, one integer, representing the answer modulo $101$.

1

2

Hint

For all testdata, $1 \leq n \leq 10^{10000000}$.

Translated by ChatGPT 5