a110. TOI 2020/05 潛力組：快樂數字

題目描述

把符合以下條件的十進位正整數稱為快樂數字：只使用 1 到 9，每個數字至少出現一次，而且任意兩個相鄰位數的差的絕對值都不超過 2。

每筆詢問給定位數 P 與最後一位 Q，請求出這樣的快樂數字共有幾個。答案對 1000000007 取餘數。

輸入格式

第一行為詢問數 N，接著 N 行各有 P、Q。

• 1 ≤ N ≤ 10000
• 1 ≤ P ≤ 1000
• 1 ≤ Q ≤ 9

輸出格式

依詢問順序，每行輸出一個計數對 1000000007 取餘數的結果。

來源

TOI 2020 年 5 月潛力組〈快樂數字〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202005/Happy-Number.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=f171