CSES 3169 ↗

Counting LCM Arrays

Number of positive arrays of length `n` with `lcm (a i) (a (i+1)) = k` throughout, modulo `10^9 + 7`.

1
submissions
1.000
best score

Given two integers n and k, your task is to count the number of arrays a1,a2,…,an of positive integers where lcm⁡(ai,ai+1)=k for all 1≤i<n.

Input

The first line has an integer t: the number of test cases.

The next t lines have two integers n and k: the length of the array and the value of lcm.

Output

Print t integers: the answer to each test case modulo 109+7.

Constraints

  • 1≤t≤1000
  • 2≤n≤109
  • 1≤k≤109

Example

Input:

3
3 4
4 6
1337 42

Output:

11
64
602746233

Explanation: The arrays for the first test case are [1,4,1], [1,4,2], [1,4,4], [2,4,1], [2,4,2], [2,4,4], [4,1,4], [4,2,4], [4,4,1], [4,4,2] and [4,4,4].

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/CountingLCMArrays/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
1,143,785,1231,143,785,123

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.0001,143,785,123talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 11:28 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.