SGAME5

vinhntndu

SPyofgame là một điệp viên của tổ chức O.W.C.A với bí danh H (H là gì thì chắc ai cũng nhận ra). Mỗi tháng, anh ta nhận được một danh sách nhiệm vụ của mình. Dù là thành viên lâu năm nhưng SPyofgame khá lười biếng, suốt ngày chỉ lo chơi surviv và nhắn tin cho bạn gái, anh ta không thể tính toán được xác suất để hoàn thành được ~N~ nhiệm vụ cụ thể được giao nên thường bị phạt tiền. Lần này, bạn hãy giúp anh ấy tính xác suất để anh ấy có thể hoàn thành được nhiệm vụ.

INPUT:

Dòng đầu tiên là số nguyên dương ~N~, số lượng nhiệm vụ được giao ~(1 \leq N \leq 20)~ ~N~ dòng tiếp theo, mỗi dòng bao gồm ~N~ số nguyên dương ~x~ là xác xuất(%) để hoàn thành được nhiệm vụ con thứ ~i~ ~(1 \leq i \leq N, 0 \leq x \leq 100)~

OUTPUT:

1 dòng duy nhất là xác suất để SPyofgame có thể hoàn thành ~N~ nhiệm vụ, đáp án được chấp nhận nếu sai số không quá ~10^{-6}~

Ví dụ:

INPUT

3
10 6 4
4 2 10
25 12 7

OUTPUT

0.150000000000

Giải thích ví du:

  • Ở nhiệm vụ 1, SPyofgame có thể nhận nhiệm vụ con thứ 2 với xác suất thành công là ~6~%
  • Ở nhiệm vụ 2, SPyofgame có thể nhận nhiệm vụ con thứ 3 với xác suất thành công là ~10~%
  • Ở nhiệm vụ 3, SPyofgame có thể nhận nhiệm vụ con thứ 1 với xác suất thành công là ~25~%

→ Tổng xác suất thành công của nhiệm vụ là 0.06 x 0.1 x 0.25 = 0.0015 = 0.15%

Không có cách nhận nhiệm vụ nào có xác suất thành công cao hơn 0.15%

Giới hạn:

  • Subtask 1: 25% số test có N ≤ 5
  • Subtask 2: 50% số test có N ≤ 10
  • Subtask 3: 75% số test có N ≤ 15
  • Subtask 4: không có giới hạn gì thêm

CJ và Catalina

hhoangcpascal

Sau khi làm nhiệm vụ cho nhóm C.R.A.S.H, thì giờ đây CJ đã không còn làm được gì, cả không thể về lại nơi cũ vì sẽ bị nhóm này truy sát. Trong lúc CJ đang đi quanh quẩn nơi đây thì vô tình gặp Catalina và cô gái này rất là hám tiền. CJ và Catalina bắt tay với nhau, và Catalina nhờ CJ giúp một công việc: Cướp hết ngân hàng nhỏ ở các khu vực nông thôn.

Ở vùng nông thôn San Andreas có ~N~ địa điểm, trong đó có ~K~ địa điểm là ngân hàng, đánh số từ ~1~ tới ~N~, và ~M~ con đường hai chiều, đánh số từ ~1~ tới ~M~, con đường thứ ~i~ có độ dài là ~L_i~. Catalina muốn CJ tìm đường đi sao cho xuất phát từ một ngân hàng, cướp hết tất cả ~K~ ngân hàng, mỗi con đường và một địa điểm có thể được đi qua nhiều lần, và độ dài đường đi là ngắn nhất có thể. Đảm bảo hai ngân hàng khác nhau bất kì đều có đường đi.

Yêu cầu: Hãy tìm ra cho CJ và Catalina độ dài đường đi ngắn nhất trên.

Dữ liệu vào: Gồm ~M + 2~ dòng:

  • Dòng đầu tiên chứa ba số nguyên dương ~N, M, K~ thể hiện số địa điểm, số con đường hai chiều, số ngân hàng.
  • Dòng tiếp theo chứa ~K~ số ~a_1, a_2, …, a_K~ là số hiệu của các địa điểm là ngân hàng.
  • ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i~, ~v_i~, ~L_i~ thể hiện có đường nối trực tiếp ~u_i, v_i~ và độ dài là ~L_i~.

Kết quả: Ghi ra độ dài đường đi ngắn nhất.

Ví dụ:

Input:

6 6 2
1 4 
3 2 1
5 4 3
5 1 1
1 2 7
3 5 3
6 1 1

Output:

4

Giới hạn:

  • ~30~% số test đầu tiên có ~N \leq 10^3, M \leq 2.10^3, K \leq 10~.
  • ~30~% số test tiếp theo có ~N \leq 10^5, M \leq 2.10^5, K \leq 10~.
  • ~40~% số test còn lại có ~N \leq 10^5, M \leq 2.10^5, K \leq 18~.

Chú ý: Chả có gì chú ý trong bài này.

CSES - Digit Queries | Truy vấn chữ số

Flower_On_Stone, SPyofgame, CatTuong

Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần:

~12345678910111213141516171819202122232425 \ldots~

Nhiệm vụ của bạn là xử lí ~q~ truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ ~k~ trong xâu?

Input

  • Dòng đầu tiên chứa một số nguyên duy nhất ~q~: số lượng truy vấn.
  • Sau đó gồm ~q~ dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên ~k~: vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ ~1~).

Output

  • Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

  • ~1 \le q \le 1000~
  • ~1 \le k \le 10^{18}~

Example

Sample input

3
7
19
12

Sample output

7
4
1

inftab

vinhntndu

Cho một bảng có số hàng và số cột là vô hạn. Các giá trị của các ô trong bảng được tính theo các quy tắc sau: Với ~i~ là chỉ số hàng, ~j~ là chỉ số cột, ta có:

  • ~A[i][1] = i~
  • ~A[i][j] = A[i][j-1] + INV(A[i][j-1])~ ~\forall j > 1~

Với ~INV(A)~ là hàm đảo ngược số ~A~. Ví dụ, ~INV(104) = 401, INV(200) = 002 = 2~.

Các số đầu tiên của bảng: enter image description here

Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~A~ và ~B~. Bạn hãy đếm số lần xuất hiện các số trong khoảng ~[A,B]~ trên bảng đó.

INPUT

  • Dòng đầu tiên là số nguyên dương ~Q~, số lượng truy vấn ~(1 ≤ Q ≤ 10^5)~
  • ~Q~ dòng tiếp theo, mỗi dòng là hai số nguyên dương ~A,B (1 ≤ A ≤ B ≤ 10^{10})~

OUTPUT

  • Gồm ~Q~ dòng, mỗi dòng là kết quả của truy vấn.

Ví dụ

INPUT

2
1 3
4 8

OUTPUT

4
11

Giải thích ví dụ:

  • Trong khoảng [1;3], số 1 xuất hiện 1 lần, số 2 xuất hiện 2 lần, số 3 xuất hiện 1 lần nên tổng số lần xuất hiện là 4
  • Trong khoảng [4;8], số 4 xuất hiện 3 lần, số 5 xuất hiện 1 lần, số 6 xuất hiện 2 lần, số 7 xuất hiện 1 lần, số 8 xuất hiện 4 lần nên tổng số lần xuất hiện là 11

Giới hạn: ~50~% số test có ~A,B~ ~\leq~ ~10^6~

[Python_Training] Giá trị nhỏ nhất đơn giản

jumptozero
  • Cho ~3~ số nguyên dương ~a,b,c~. Đặt ~S=min\left\{a+b,b+c,c+a\right\}~, xuất ~S~ ra màn hình.

Input:

  • Dòng thứ nhất chứa ~3~ số nguyên dương ~a,b,c(1\le a,b,c\le 10000)~

Output:

  • In ra ~S~ cần tìm.

Ví dụ:

Input:

2 5 6

Output:

7

Nguồn: Atcoder

Tiền tệ

Small

Ông Lionheart - thị trưởng của Bilaspur, có một kế hoạch cho cư dân của mình. Ông ta muốn giới thiệu một hệ thống tiền tệ chỉ gồm 2 loại tiền mệnh giá ~a~ đồng và ~b~ đồng. Nhưng có một vấn đề rắc rối là có những khoản tiền không thể chi trả bằng cách chỉ sử dụng 2 loại tiền này. Trong những trường hợp đó, công dân sẽ phải chọn thanh toán kỹ thuật số.

Cho ~n~ khoản tiền, bạn hãy cho biết có bao nhiêu khoản tiền có thể thanh toán được bằng cách sử dụng các loại tiền trên và còn bao nhiêu khoản tiền phải được thanh toán bằng kỹ thuật số. Biết rằng thị trưởng đã cung cấp không giới hạn các loại tiền này.

Dữ liệu

  • Dòng đầu tiên chứa 3 số nguyên ~n, a, b~ (~1 ≤ n, a, b ≤ 10^5~).
  • Dòng thứ hai chứa ~n~ số nguyên ~c_i~, mô tả ~n~ khoản tiền cần thanh toán (~1 ≤ c_i ≤ 10^5~).

Kết quả

  • Ghi ra một dòng chứa 2 số nguyên tương ứng là số khoản tiền có thể thanh toán bằng 2 loại tiền mệnh giá ~a~ đồng, ~b~ đồng và số khoản tiền phải thanh toán bằng kỹ thuật số.

Sample input

5 4 6
16 20 36 22 15

Sample output

4 1

Sample input

7 7 5
7 25 14 27 45 34 41

Sample output

7 0

Giải thích:

  • Ví dụ 1. Có 4 khoản tiền thanh toán được bằng 2 loại tiền mệnh giá 4 đồng và 6 đồng là: 16, 20, 36, 22. Khoản tiền 15 không thanh toán được qua 2 loại tiền trên nên phải thanh toán bằng kỹ thuật số.
  • Ví dụ 2. Tất cả các khoản tiền đều thanh toán được qua 2 loại tiền mệnh giá 7 đồng và 5 đồng.

Ràng buộc

  • Subtask 1 (30%): ~1 ≤ n, a, b, c_i ≤ 10^2.~
  • Subtask 2 (30%): ~1 ≤ n, a, b, c_i ≤ 10^3.~
  • Subtask 3 (40%): Như ràng buộc gốc.

Nguồn: codechef

Cánh diều - KILOPOUND - Đổi kilo ra pound

DKingQA, Flower_On_Stone, habelle

Cho một số là khối lượng ở đơn vị ~ki-lo-gam~. Hãy đổi sang đơn vị ~pound~ biết rằng ~1kg = 2.205 pound~.

Input:

Một số thực là khối lượng ở đơn vị ~kg~.

Output:

Một số thực là giá trị ở đơn vị ~pound~ được quy đổi. Lấy 2 số phần thập phân.

Ví dụ:

Sample Input

4.5

Sample Output

9.92

CSES - Counting Sequences | Đếm dãy số

nhphucqt

Đếm số dãy có độ dài ~n~ mà trong đó mỗi phần tử là một số nguyên từ ~1… k~ và mỗi số nguyên từ ~1… k~ xuất hiện ít nhất một lần trong dãy.

Ví dụ, khi ~n = 6~ và ~k = 4~, một số dãy hợp lệ là ~[1,3,1,4,3,2]~ và ~[2,2,1,3,4,2]~.

Input

  • Một dòng duy nhất chứ 2 số nguyên ~n~ và ~k~.

Output

  • Một số nguyên duy nhất: số dãy có thể tạo được sau khi modulo cho ~10^9 + 7~.

Constraints

  • ~1\leq k \leq n \leq 10^6~

Example

Sample Input

6 4

Sample Output

1560

Tặng hoa

Small

Nhân dịp ngày Quốc tế phụ nữ (8-3), các bạn nam trong lớp quyết định mua hoa tặng các bạn nữ trong lớp mình. Tuy nhiên, đây là một kế hoạch tự phát, mỗi bạn nam tự mình đi mua hoa không bàn bạc với bạn khác. Chính vì vậy cuối cùng có ~M~ loại hoa khác nhau được đem đến lớp (các loại hoa đánh số từ 1 đến ~M~), loại hoa thứ ~i~ có ~a_i~ bông hoa.

Một vấn đề đau đầu được đặt ra cho lớp trưởng - một bạn nam đẹp trai nhất trong lớp- là làm thế nào chia các bông hoa này cho các bạn nữ trong lớp để số bông hoa của bạn nữ nhận được nhiều hoa nhất là nhỏ nhất (bặc biệt là bạn nữ mà lớp trưởng yêu thích). Biết rằng mỗi bạn nữ chỉ nhận các bông hoa cùng một loại (hoặc không nhận được bông hoa nào).

Yêu cầu: Viết chương trình tính số lượng hoa của bạn nữ nhận được nhiều hoa nhất trong phương án trên.

Dữ liệu vào

  • Dòng đầu tiên ghi hai số nguyên dương ~N~ (~1 \le N \le 10^9~) là số lượng bạn nữ trong lớp và ~M~ (~1 \le M \le 10^6; M \le N~) là số lượng loại hoa khác nhau
  • ~M~ dòng tiếp theo, dòng thứ ~i~ ghi số ~a_i~ là số lượng hoa của loại hoa thứ ~i~ (~1 \le a_i \le 10^9~)

Kết quả

  • Một số nguyên duy nhất là số bông hoa của bạn nữ nhận được nhiều hoa nhất trong phương án tối ưu (là phương án mà số hoa của bạn nữ có nhiều hoa nhất là nhỏ nhất)

Sample Input 1

5 2
7 
4

Sample Output 1

3

Giải thích:

  • 7 bông hoa đầu chia cho 3 bạn với số lượng là ~3; 2; 2~;
  • 4 bông hoa đầu chia cho 2 bạn với số lượng là ~3; 1~ hoặc ~2; 2~;

Sample Input 2

7 5
7
1
7
4
4

Sample Output 2

4

Giới hạn

  • Có 50% test ~n ≤ 10^4~.
  • Có 25% test ~n ≤ 10^6~.

Nguồn: 2019 CBN

Robot

Small

Cho lưới ô vuông kích thước ~n~ dòng và ~n~ cột. Các dòng của lưới được đánh số từ 1 đến ~n~. Các cột của lưới cũng được đánh số từ 1 đến ~n~. Ô nằm trên giao của dòng ~i~ và cột ~j~ của lưới được gọi là ô (~i,j~) và (~i, j~) được gọi là tọa độ của nó. Mỗi ô của lưới chứa một số thuộc tập {~0, 1~}. Ô chứa số ~0~ được gọi là ô tự do còn ô chứa số ~1~ được gọi là ô bị cản. Robot được đặt ở ô (~L_1,C_1~) cần phải di chuyển đến ô (~L_2,C_2~). Robot chỉ có thể di chuyển theo hướng thẳng đứng hoặc hướng nằm ngang.

Yêu cầu: Cần xác định:

  1. Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (~L_1,C_1~) tới ô (~L_2,C_2~)
  2. Số lần đổi hướng ít nhất để robot có thể di chuyển từ ô (~L_1,C_1~) tới ô (~L_2,C_2~) trong tình huống được phép biến một ô bị cản thành ô tự do.
  3. Số lượng các ô bị cản mà việc loại bỏ bất cứ một ô nào trong số chúng, ta đều đạt được số lần đổi hướng như trong câu 2).

Dữ liệu

  • Dòng thứ nhất chứa số nguyên ~n,(<n< 1000)~; 
  • ~n~ dòng tiếp mỗi dòng chứa ~n~ số ~0~ hoặc ~1~ được ghi cách nhau bởi dấu cách mô tả trạng thái của lưới; • Dòng thứ ~n+2~ chứa 4 số ~L_1,C_1, L_2,C_2~ (đảm bảo là các ô (~L_1,C_1~) và (~L_2,C_2~) là các ô tự do).

Kết quả

  • Ghi ra ba số nguyên là các câu trả lời cho 3 yêu cầu tương ứng nêu trong đầu bài.

Sample input

5
0 1 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 0 1 0
0 0 0 0 0
1 1 1 5

Sample output

4 2 2

enter image description here


Nguồn: Thầy Nghĩa '18

Nhảy về đích (HSG11v2-2022)

Small

Bài 2: Nhảy về đích (7 điểm)


Phân số nhỏ nhất (THTA Vòng sơ loại 2022)

Flower_On_Stone

Cho ba số tự nhiên ~A, B, C~. Từ ba số đó, hãy tạo ra một phân số nhỏ nhất có thể. In ra tổng của tử số và mẫu số của phân số nhỏ nhất đã được tối giản.

Input

  • Ba tự nhiên ~A, B, C~ ~(0 < A, B, C \leq 1000)~, mỗi số trên một dòng.

Output

  • In ra một số duy nhất là kết quả của bài toán.

Example

Sample input

3
2
4

Sample output

3

Note

Những phân số có thể tạo ra: ~\dfrac{3}{2}; \dfrac{3}{4}; \dfrac{2}{3}; \dfrac{2}{4}; \dfrac{4}{3}; \dfrac{4}{2}~

Phân số bé nhất là ~\dfrac{2}{4} = \dfrac{1}{2}~

Vậy kết quả là ~1 + 2 = 3~

Đếm hoán vị

cuom1999

Cho hai số nguyên dương ~n, k~. Đếm xem có bao nhiêu hoán vị ~p_1, p_2, ..., p_n~ của ~1, 2, ..., n~ thỏa mãn ~p_i > p_{i / k}~ với mọi ~1\leq i\leq n~.

Trong đó, ~a/b~ là số nguyên lớn nhất không vượt quá ~\dfrac{a}{b}~ và quy ước ~p_0 = 0~.

Input

Gồm hai số nguyên dương ~n, k \ (1 \leq n, k \leq 10^6)~

Output

In ra số lượng hoán vị thỏa mãn điều kiện sau khi ~\mod (10^9+7)~

Sample Input 1

3 2

Sample Output 1

2

Sample Input 2

8 3

Sample Output 2

2520

Giải thích

Trong test 1, chúng ta cần tìm các hoán vị thỏa mãn ~p_3>p_1~ và ~p_2>p_1~. Có 2 hoán vị như vậy ~(1, 2, 3)~ và ~(1, 3, 2)~.

Giới hạn

  • ~20~% test có ~n \leq 10~
  • ~10~% test có ~k > n~
  • ~10~% test có ~k = n~
  • ~20~% test có ~k > \frac{n}{2}~
  • ~20~% test có ~n, k \leq 10^3~
  • ~20~% test có ~n, k \leq 10^6~

Đếm tập hợp

jumptozero

Cho ~n~ tập hợp ~A_1,A_2,...,A_n~ biết rằng, tất cả các phần tử trong mỗi tập hợp đã cho đều thuộc đoạn ~[1;m]~ và các phần tử trong mỗi tập hợp đều khác nhau từng đôi một !

Yêu cầu: Hỏi ta có thể tạo thành được bao nhiêu tập hợp khác nhau bằng cách lấy một vài tập hợp từ ~n~ tập hợp đã cho hợp lại với nhau.

Input:

  • Dòng thứ nhất chứa số ~t(1\le t\le 50)~ - Thể hiện số testcase

  • ~t~ block tiếp theo, mỗi block có dạng như sau:

    • Dòng thứ nhất chứa hai số nguyên ~n,m(1\le n\le 100,1\le m\le 14)~

    • ~n~ dòng tiếp theo, mỗi dòng gồm ~k+1(k\le m)~ số nguyên trong đó: Phần tử đầu tiên thể hiện số lượng phần tử của tập hợp ~A_i~ và ~k~ phần tử tiếp theo - thể hiện các phần tử của tập ~A_i~

Output:

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Ví dụ:

Input:

2
2 3
1 1
2 1 3
2 4
2 2 3
2 1 4

Output:

2
3

Giải thích:

  • Ứng với testcase 1, ta chỉ có thể tạo ra được 2 tập khác nhau đó là: ~\left\{1\right\}~ ; ~\left\{1,3\right\}~

  • Ứng với testcase 2, ta chỉ có thể tạo ra được 3 tập khác nhau đó là: ~\left\{2,3\right\}~ ; ~\left\{1,4\right\}~ ; ~\left\{1,2,3,4\right\}~

Subtask:

  • ~10\text{%}~ : ~1\le n\le 20~

  • ~90\text{%}~ : Không có điều kiện gì !

Xâu song sinh (THT C1 Đà Nẵng 2022)

Small

Bài 1: Xâu song sinh

.

[enter link description here][1]

Nâng cấp đường (OLP 10 - 2019)

Small

Hành tinh Marvelous Land gồm ~N~ thành phố, được kết nối với nhau bởi ~M~ tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới ~N~. Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố ~N~. Tuyến đường thứ ~i~ cho phép đi lại giữa hai thành phố ~u_i~ và ~v_i~ với ~t_i~ đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố ~N~ với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Dữ liệu

  • Dòng đầu chứa hai số nguyên ~N~ và ~M~ (~1 ≤ N ≤ 10^5, 1 ≤ M ≤ 2 × 10^5~), số thành phố và số tuyến đường.
  • ~M~ dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ ~i+1~ ghi số ~u_i, v_i, t_i~ (~1 ≤ u_i, v_i ≤ N, 1 ≤ t_i ≤ 10^6~) là các thông tin của tuyến đường thứ ~i~.

Kết quả

  • Ghi ra duy nhất một số nguyên là số tuyến đường trọng yếu.

Input

8 9
1 2 3
1 3 1
2 4 4
3 4 7
5 4 9
8 6 5
8 7 4
6 5 2
7 5 3

Output

3

Ràng buộc: 50% số điểm của bài tương ứng với các test có ~N ≤ 1000~ và ~M ≤ 1000~


Nguồn: Olympic 30/4 năm 2019.

Trie - PREFIX

Small

Một xâu được gọi là xâu tiền tố của một xâu khác nếu nó xuất hiện ở vị trí đầu tiên của xâu này.

Ví dụ xâu ab là tiền tố của xâu abcd; aa là tiền tố của aa

Yêu cầu: Cho ~n~ xâu ký tự, hãy đếm số cặp xâu mà xâu này là tiền tố của xâu còn lại

Input

  • Dòng đầu tiên ghi số nguyên dương ~n\ (1≤n≤10^6)~
  • ~n~ dòng tiếp theo, mỗi dòng ghi một xâu ký tự chỉ gồm các chữ cái tiếng Anh in thường với độ dài của mỗi xâu không vượt quá ~10~

Output

  • In ra một số nguyên duy nhất là số lượng xâu tìm được.

Example

Sample Input:

4
abc
aa
aab
aa

Sample Output:

3
Chuyên đề DHBB 2021

Chia hết và không chia hết

jumptozero, tkluannguyendang

Viết chương trình tìm tất cả các số chia hết cho ~3~ nhưng không phải bội số của ~5~, nằm trong đoạn ~1~ và ~n~(tính cả ~1~ và ~n~). Các số thu được sẽ được in thành chuỗi trên một dòng, cách nhau bằng dấu cách.

Input:

  • Một dòng duy nhất chứa số ~n(1\le n\le 5000)~

Output:

  • In ra đáp án cần tìm

Ví dụ:

Input:

10

Output:

3 6 9

Bán bánh dày

Toilaaibanbietko7A4, nguyenminhhai021009
"Mừng tết đến và lộc đến nhà nhà
Cánh mai vàng , cành đào hồng thắm tươi
Chúc cụ già được sống lâu sống thọ
Cùng con cháu sang năm lại đón tết sang
Và kính chúc người người sẽ gặp lành
Tết sau được nhiều lộc hơn tết nay
Tết đến đoàn tụ cùng ở bên bếp hồng
Và nồi bánh chưng xanh , chờ xuân đang sang ..."

Ở một góc phố, bài hát do Bích Phương thể hiện "Long phụng sum vầy" lại vang lên nhân dịp Tết đến xuân về, dù chưa tới Tết hihi. Đó là ở tiệm bánh dày của Nguyên Toilaaibanbietko7A4 tôi. Dạo này quán tôi buôn bán phát đạt lắm, ngày nào cũng làm cả đống bánh mà bán vẫn hết không dư cái nào, có khi còn thiếu nữa. Bánh tôi làm rất ngon, tiếng lành đồn xa, ai ai cũng thích cả. Quay lại chuyện hôm ấy, một ngày vẫn như mọi ngày, bánh quán tôi bán vẫn đắt như tôm tươi.

Thế bỗng nhiên, có ông khách đại gia tên Hải nguyenminhhai021009 tới mua bánh. Mà khổ nỗi, ổng không mua bánh theo kiểu thường. Ổng muốn bánh ổng mua phải được xếp thành hình tứ diện đều, các chiếc bánh xếp tháp phải xít nhau nhất có thể nhưng không được méo mó cái nào, sao cho độ cao của cái tháp ấy phải đúng bằng ~H~. Nghe thấy xong tôi hoảng hồn luôn, vì biết làm bao nhiêu cái bánh dày cho đủ chứ. Các bạn ơi, hãy giúp tôi tìm số bánh dày tối thiểu mà tôi cần làm để xếp được cái tháp tứ diện sao cho độ cao của nó phải gần độ cao ~H~ nhất có thể thỏa theo đúng yêu cầu của ông Hải nhé. Biết rằng bánh tôi làm luôn là hình tròn và cái bánh tôi làm có đường kính là ~d~

Lưu ý: Chỉ 1 chiếc bánh mà có thể thỏa mãn điều kiện ~H~ thì vẫn đưa được cho ông Hải nhé, đừng nhầm :D

Dữ liệu:

  • Dòng 1 gồm 1 xâu S. Xâu này chẳng để làm gì cả, chỉ là tôi muốn gửi lời chúc Tết đến các bạn thôi hihi :))
  • Dòng 2 gồm 2 số là ~H~ và ~d~.

Kết quả: Gồm 1 dòng duy nhất là số bánh dày tôi cần làm. Kết quả có thể rất lớn nên kết quả cần được ~\mod 10^9+7~

Giới hạn:

  • ~1≤d≤H≤10^{12}~

Sample test

1

Input

Happy_New_Year_!
1 1

Output

1

Minh họa:

(Hình ảnh VD với d=3 và giả dụ số tầng bánh là 2, số bánh là 4)

P/s: Chúc mừng năm mới!!!