Credit Card Validation using the Luhn Algorithm

This problem requires you to validate a credit card number using the Luhn algorithm. The algorithm works by processing the digits from right to left, doubling every second digit, and subtracting 9 when the doubled value exceeds 9. Formally, let a credit card number be represented as a sequence of digits \(d_n, d_{n-1}, \dots, d_1\). For each digit, calculate an adjusted value \(a_i\) defined as follows:

\(a_i = \begin{cases} d_i, & \text{if it is not doubled} \\ 2d_i - 9, & \text{if doubling results in a number greater than 9} \end{cases}\)

Then compute the sum: \(S = \sum_{i=1}^{n} a_i\). The credit card number is considered valid if \(S \equiv 0 \pmod{10}\); otherwise, it is invalid.

inputFormat

The input consists of a single line containing a string of digits that represents the credit card number.

outputFormat

Output a single line containing either Valid if the number is valid according to the Luhn algorithm, or Invalid if it is not.

## sample

4532015112830366

Valid

</p>