Trong hành trình chinh phục những vì sao, kỵ sĩ Luna phải băng qua một cánh đồng có hình chữ nhật kích thước ~n \times m~. Kỵ sĩ cưỡi trên một con ngựa, xuất phát từ ô ~(1,1)~ ở góc dưới bên trái để đi đến trên điểm cuối của cánh đồng ở góc trên bên phải. Con ngựa này có thể nhảy những bước giống như mã trên bàn cờ vua, tức là từ ô ~(a,b)~ có thể nhảy đến ô ~(c,d)~ mà ~|(a-c)(b-d)|=2.~ Hãy giúp kỵ sĩ đếm xem có bao nhiêu cách để băng qua cánh đồng này nhé, biết rằng con ngựa chỉ nhảy sang phải và hướng lên trên, không bao giờ đi lùi bước.

Input: một dòng duy nhất gồm hai số nguyên dương ~n,m~ trong đó ~1 \le n, m \le 10^6.~

Output: đáp số của bài toán, chia dư cho ~10^9+7.~

Sample input 1:

4 4

Sample output 1:

2

Sample input 2:

2023 2023

Sample output 2:

320887707

Vào dịp lễ tình nhân, anh chàng đào hoa Phú Lâm đã gửi ~n~ bức thư chúc mừng đến ~n~ người yêu của mình (giả sử tên của họ đều khác nhau). Tuy nhiên, đáng tiếc là Phú đã mắc nhầm lẫn không hề nhẹ nên đã gửi sai địa chỉ hết các bức thư, vì thế cô ~X~ thì nhận thư của cô ~Y~, cô ~Y~ thì nhận thư của cô ~Z~, ... Thế là sau đợt lễ đáng nhớ đó, cả ~n~ cô gái đã cùng chia tay Phú Lâm. Câu hỏi đặt ra là Phú có bao nhiêu cách thực hiện lỗi sai đó, tức là gửi thư cho các cô gái mà không ai nhận đúng lá thư của họ?

Input

Số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^6.~

Output

Kết quả của bài toán, lấy modulo ~10^9+7.~

Sample input 1

4

Sample output 1

9

Sample input 2

12345

Sample output 2

137669039

Việc học lập trình thuật toán thật sự rất cô đơn, Ali Vũ nhận thấy mình và các bạn bè trong lớp chuyên Tin cùng trang lứa cũng giống như các số nguyên tố. Mỗi người mỗi nơi, ít khi có dịp nào làm chung với nhau công việc gì. Các số nguyên tố cũng vậy, tách rời nhau và gần như không có số nào đứng cạnh nào trong dãy số tự nhiên. Để làm rõ hơn điều đó, Vũ bèn rủ bạn Ban cùng lớp chơi một trò chơi như sau: Vũ sẽ viết lên bảng các số nguyên dương từ 1 đến ~n~ theo thứ tự tùy ý, và Ban sẽ đếm xem có bao nhiêu cặp số nguyên tố đứng cạnh nhau trong dãy đó. Một điều thú vị là kết quả thu được cũng không tệ, tức là số cặp nguyên tố cạnh nhau cũng khá nhiều, dù Vũ đã thử viết lên nhiều thứ tự khác nhau. Vì thế, Vũ đổi lại luật lại tí xíu: Vũ sẽ viết các số lên bảng sao cho chẵn, lẻ xen kẽ nhau và nhờ Ban đếm lại. Quả thật, số cặp số nguyên tố đứng cạnh nhau đã giảm đi rõ rệt đúng như Vũ mong muốn.

Yêu cầu: hãy giúp Vũ tính xem khi xét tất cả các cách viết có thể có, mỗi cách là một hoán vị chẵn lẻ xen kẽ của các số ~1,2,...,n~ thì tổng số các cặp số nguyên tố đứng cạnh nhau là bao nhiêu?

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^7.~

Output

Kết quả của bài toán, lấy modulo ~10^9+7.~

Sample input

4

Sample output

6

Giải thích

Các hoán vị có thể có với số cặp tương ứng là: ~(1, 2, 3, 4)~: ~1~ cặp, ~(3, 2, 1, 4)~: ~1~ cặp, ~(1, 4, 3, 2)~: ~1~ cặp, ~(3, 4, 1, 2)~: ~0~ cặp, ~(2, 1, 4, 3)~: ~0~ cặp, ~(2, 3, 4, 1)~: ~1~ cặp, ~(4, 1, 2, 3)~: ~1~ cặp, ~(4, 3, 2, 1)~: ~1~ cặp. Tổng cộng có ~6~ cặp thỏa mãn.

Ràng buộc

• Có ~20\%~ số test ứng với ~n \le 12.~
• Có ~50\%~ số test ứng với ~n \le 10^4~ và ~n~ chẵn.
• Có ~30\%~ số test ứng với ~n \le 10^7.~

Lộc đang được đào tạo để trở thành một chuyên gia đánh máy hàng đầu cho dự án IUH Coder. Leader của em ấy đã giao một nhiệm vụ về nhà là đánh máy một xâu ký tự in hoa "F", "O" và "X". Lộc đang ăn kem que vào một chiều đông nóng bức và vẫn hy vọng hoàn thành nhiệm vụ này thật nhanh. Em ấy muốn cầm que kem bằng một tay và gõ bằng tay kia. Thật không may, Lộc vẫn còn là một cậu bé mới lớn và mỗi bàn tay của cậu quá nhỏ để có thể chạm hết bàn phím. Em chỉ có thể chạm tới các chữ cái "F" và "X" bằng tay trái và các chữ cái "F" và "O" bằng tay phải.

Xét một xâu ~W~ mà Lộc phải gõ. Lộc có thể bắt đầu gõ bằng bất kỳ tay nào (tay kia cầm que kem). Sau đó, có thể em phải đổi tay nếu cần để gõ các chữ cái theo đúng thứ tự. Gọi ~F(W)~ là số lần tối thiểu Lộc phải đổi tay để gõ một xâu ~W~ như vậy (trong suốt quá trình đó, một tay em luôn cầm que kem và gõ bằng tay còn lại). Ví dụ: nếu ~W = XXFFOOF~ thì Lộc cần phải đổi tay ít nhất ~1~ lần: gõ ~X,X,F,F~ bằng tay trái, rồi đổi tay để gõ ~O,O,F~ bằng tay phải; còn nếu ~W = OOOOO~ thì Lộc không cần đổi tay lần nào cả.

Yêu cầu đặt ra là cho một xâu ~S~ có độ dài ~N~, gọi ~G(S)~ là tổng của ~F(W)~ trên tất cả các xâu con ~W~ của ~S~ (xâu con là một tập con các ký tự liên tiếp của xâu ban đầu). Lưu ý rằng có tất cả ~1+2+...+N = \frac{N(N+1)}{2}~ xâu con như vậy. Hãy giúp Lộc tính giá trị của ~G(S)~ modulo ~10^9+7.~

Input: dòng đầu tiên gồm số ~N~ là độ dài của xâu với ~1 \le N \le 8.10^5~, dòng tiếp theo là xâu cần gõ.

Output: kết quả của bài toán.

Sample input 1:

3

XFO

Sample output 1:

1

Sample input 2:

10

FXXFXFOOXF

Sample output 2:

36

Giải thích:

Ta thấy rằng chuỗi ~XFO~ có các chuỗi con là: ~X, F, O, XF, FO, XFO~ trong đó chỉ có chuỗi cuối mới cần đổi tay để gõ, còn lại hoàn toàn có thể gõ bằng 1 tay.

Cho số nguyên dương ~n,k~. Một dãy số nguyên dương có độ dài ~k~ được gọi là tốt nếu như ~a_1 = n~ và ~a_i~ chia hết cho ~a_{i+1}~ với mọi ~1 \le i \le k-1.~

Yêu cầu đặt ra là đếm số dãy như thế.

Input

Một dòng duy nhất gồm số ~n,k~ với ~1 \le n, k \le 10^{15}.~

Output

Đáp số của bài toán, lấy modulo ~10^9+7.~

Sample input

6 3

Sample output

9

Giải thích

Trong VD, ta có thể liệt kê ra các dãy là: ~(6,6,6),(6,6,3),(6,6,2),(6,6,1),(6,3,3),(6,3,1),(6,2,2),(6,2,1),(6,1,1).~

Subtasks

• Có ~50\%~ test của đề ứng với ~n \le 10^6, k \le 20.~
• Có ~50\%~ test của đề ứng với ~10^6 < n \le 10^{15}, 20 < k \le 10^{15}.~

Trong truyền thuyết của CLB H3.2 viết, những con cá hồi có thể vượt qua nhiều vũ môn để trở thành InfinitySalmon. Mỗi vũ môn là một chặng đường phấn đấu trong cuộc đời của con cá hồi và được đại diện bởi một con số nguyên dương. Như vậy các vũ môn sẽ tạo thành một dãy gồm ~n~ số nguyên dương tăng ngặt và vũ môn cuối cùng có giá trị không vượt quá ~m~. Con cá hồi trong câu chuyện hôm nay khá đặc biệt, nó thích trong lần thứ ~i~ (với ~1 \le i \le n~) thì giá trị vũ môn nó vượt qua sẽ có cùng số dư với ~i^2~ khi chia cho ~k~. Bạn hãy giúp con cá hồi đếm xem có bao nhiêu cách để trở thành InfinitySalmon nhé, do kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Input

Một dòng duy nhất gồm ba số nguyên dương ~n,m,k~ trong đó ~1 \le n \le 10^5~, ~1 \le m \le 10^9~, ~1 \le k \le 10^6~.

Output

Đáp số của bài toán.

Sample input 1.

2 4 2

Sample output 1.

3

Sample input 2.

12 2021 12

Sample output 2.

608212426

Giải thích. Trong VD1, con cá hồi có thể nhảy với các cách là: ~1 \to 2~ hoặc ~1 \to 4~ hoặc ~3 \to 4~.

Sau kỳ thi UCPC 2023 mà không nhận được món quà nào (dù đã rất cố gắng), Mạnh cũng đã trở nên hướng nội. Bạn ấy muốn đến lab H3.2 vào một ngày mà không gặp mặt ai, để gặm nhấm sự cô đơn và mau quên bớt nỗi buồn. Trong CLB H3.2, có tất cả ~n~ thành viên và họ không đi đến lab mọi lúc mọi nơi. Thành viên thứ ~i~ sẽ đến lab sau mỗi ~a_i~ ngày. Hôm nay có một thời điểm mà tất cả thành viên của CLB họp mặt để bàn kế hoạch xem Code camp mùa tới sẽ làm ở đâu và có mặt đông đủ các thành viên. Có một điều thú vị là sau không quá ~50~ năm nữa thì tất cả sẽ lại cùng có mặt ở lab ~(*).~ Hỏi trong ~m~ ngày sắp tới, trước khi Mạnh hết buồn, có bao nhiêu ngày mà bạn ấy có thể lên CLB và được ở một mình, cô đơn trọn vẹn?

Input

Dòng đầu tiên gồm số ~n,m~ với ~1 \le n \le 10^4~ và ~1 \le m \le 10^{18}.~

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ không nhất thiết phân biệt và thỏa mãn ~(*),~ trong đó người thứ ~i~ sẽ đến thăm lab sau mỗi ~a_i~ ngày.

Output

Đáp số của bài toán.

Sample input:

2 10
2 3

Sample output:

3

Giải thích: bạn Mạnh có thể lên lab vào các ngày thứ ~1,5,7~ thì sẽ không sợ bị ai làm phiền, có tất cả ~3~ ngày. Ngoài ra, mong rằng bạn có thể chấp nhận một chút tính phi thực tế của bài toán này, vì không có ai có thể buồn hết ~10^{18}~ ngày được.

Cho số nguyên dương ~n~ và gọi ~S~ là tập hợp các ước của ~n~. Cặp số ~(a,b)~ với ~a,b \in S~ có tính thứ tự được gọi là liên kết nếu như có thể chọn số nguyên dương ~k~ nào đó để cho ~a^k+b^k~ chia hết cho ~ab~. Chú ý: cặp số có thứ tự nghĩa là ~(a,b)~ và ~(b,a)~ được coi là phân biệt nhau. Yêu cầu đặt ra là tính số lượng cặp liên kết.

Gợi ý: hai số liên kết nhau thì tập hợp các ước nguyên tố của chúng có đặc điểm gì?

Input

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Đáp số của bài toán (cho biết rằng đáp số đó sẽ biểu diễn được trong kiểu Int64).

Sample input

4

Sample output

5

Giải thích Ở Ví dụ, với ~n=4~, ta có các cặp liên kết là ~(1,1),(2,2),(4,4),(2,4),(4,2)~ nên đáp số là ~5.~

Mít và Xoài là các SV xuất sắc của thầy Luna. Sau khi dạy xong một tuyệt chiêu về phép đếm trong lập trình, thầy đã ra một bài rất tâm đắc cho Mít và Xoài làm. Hai bạn được cho bảng ô vuông kích thước ~n \times n~, mỗi ô được tô bởi một trong ba màu: xanh - đỏ - vàng sao cho không có hàng nào và không có cột nào được tô tất cả các ô bởi màu đỏ. Đánh số các hàng, cột theo thứ tự từ trái sang phải và dưới lên trên. Ban đầu có sẵn ~k~ ô được thầy Luna tô màu xanh hoặc vàng trước, cho biết danh sách tọa độ của chúng là thứ tự của hàng, cột của ô được tô. Nhiệm vụ của Mít và Xoài là đếm xem có tất cả bao nhiêu cách tô thỏa mãn điều kiện đề bài và kết quả có thể rất lớn nên lấy modulo ~10^9+7.~ Đã nhiều ngày nhưng các bạn vẫn chưa đếm xong, bạn có thể giúp hai bạn ấy được không?

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,k~ trong đó ~1 \le n \le 10~ và ~0 \le k \le \min \{ n^2, 10 \}~. Các dòng tiếp theo mô tả tọa độ của các ô được tô màu trước với dạng ~x\, y \, z~ trong đó ~x,y~ là chỉ số hàng, cột, còn ~z~ là màu: ~z=1~ là xanh, ~z=2~ là vàng.

Output

Đáp số của bài toán.

Sample input

2 0

Sample output 1

56

Sample input 2

3 2
1 1 2
2 3 1

Sample output 2

2034