For all positive integers \(x\), the function \(f(x)\) is defined as follows:

• If \(x\) has any digits that aren't \(0\) or \(1\), for each digit of \(x\), set it to \(1\) if it is odd or \(0\) otherwise, and return \(x\).
• Otherwise, return \(x-1\).

Given a value of \(x\) (\(1 \leq x < 10^{2\cdot 10^5}\)), find how many times \(f\)
needs to be applied to \(x\) until \(x\) reaches \(0\). As this number might be very
large, output its remainder when divided by \(10^9+7\).

Problem credits: Aidan Bai

SCORING

• Inputs 3-5: \(T\le 2000\), \(x< 10^{9}\)
• Inputs 6-7: \(x<10^{18}\)
• Inputs 8-9: \(x<10^{60}\)
• Inputs 10-12: No additional constraints.

Problem credits: Aidan Bai

The first line contains \(T\) (\(1\le T\le 10^5\)), the number of independent tests.

The next \(T\) lines each contain a positive integer \(x\) consisting solely of the
digits 0-9, with no leading zeros.

It is guaranteed that the total number of digits in all input integers does not
exceed \(10^6\).

For each test case, output the remainder of the number of times when divided by
\(10^9+7\) on a separate line.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > Third Contest > Bronze