you are given two numbers n and m. you need to count the number of arrays containing the elements from 1 to m that can be formed by satisfying the following conditions

1. a[i]!= a[i+1]
2. a[0]==a[n-1]

you have to answer for t queries

1<=t<=10^5
3<=n,m<=10^18

if answer is large output answer%10^9
i think this is a combinatorics problem but I'm stuck on how to proceed further.