f988: 國中排列組合
Tags : 數學 組合
Accepted rate : 3人/5人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-03 00:15

Content

阿行是個天才兒童,他在一個月大的時候就學會打電動、六個月大的時候就學會舔嘴唇、一歲時學會擺攤、一歲又六個月時學會開車兜風、一歲又十個月時去火鍋店打工、兩歲時發明了「拖椅子」的遊戲,而現在要講的,是阿行兩歲又四個月大時的故事。

阿行兩歲又四個月時,就致力於拜訪別人家園,常常因為找不到路而生氣。最近不知因為什麼事情而很開心。開車回家時,也許是因為過於疲憊,不幸追撞了黑色的高級車。對為了保護哥哥而擔下全部責任的阿行,車主所提出的和解條件是……

正當條件要開出來時,阿行使出了他靈敏的嗅覺,果然在車主身上嗅出奇怪的味道。沒錯,阿行最不能接受的就是別人臭他,他當然要反擊。車主看到阿行如此兇狠的模樣,就狼狽地逃走了。

有一天阿行找哥哥買了 1kg 的豬肉,可是阿行回家以後把豬肉放上磅秤,發現哥哥給他的豬肉竟然少了 24g。

於是阿行給了哥哥 $\color{black}{n,m}\ $,請哥哥算出 $\color{black}{C_{m}^{n}\ (mod\ 10^8+7)}\ $。

Input

第一行輸入 $\color{black}{t}\ $,代表測資筆數。

接下來 $\color{black}{t}\ $ 行,每行有兩個數 $\color{black}{n,m}\ $,代表要求 $\color{black}{C_{m}^{n}\ (mod\ 10^8+7)}\ $。

  • $\color{black}{1≤t≤10^5}\ $
  • $\color{black}{1≤m≤n≤10^{18}}\ $
Output

每行輸出答案。

Sample Input #1
5
1 1
2 1
6 2
12345 9999
12345678910 12345432101
Sample Output #1
1
2
15
76523057
16188234
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (6%): 3.0s , <1M
公開 測資點#1 (20%): 3.0s , <10M
公開 測資點#2 (74%): 3.0s , <10M
Hint :

$\color{black}{6\%:1≤t≤100}\ $

$\color{black}{20\%:1≤m≤n≤10^8}\ $

$\color{black}{74\%:無特別限制}\ $

Tags:
數學 組合
出處:
Caido [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」