ATGX - ADN

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 98M Input: bàn phím Output: màn hình

Con người có 4 loại ADN: \(A,X,T,G\). Giả sử đoạn gen quy định màu da của con người là một chuỗi \(N\) ADN kết hợp từ 4 loại ADN trên (\(1 \le N \le 20\)). Ví dụ một đoạn gen có \(8\) ADN là: \(AATXGGGT\). Các ADN trong đoạn gen được đánh số từ \(1\) đến \(N\).

Đoạn gen quy định màu da của thế hệ con cũng là một đoạn \(N\) ADN kết hợp từ gen của bố và gen của mẹ. Trong đó ADN thứ \(i\) (\(1 \le i \le N\)) được hình thành bằng cách lấy ADN thứ \(i\) tương ứng của gen bố hoặc gen mẹ.

Ví dụ:

Gen của bố: \(AATX\).

Gen của mẹ: \(GATT\).

Gen của con chỉ có thể là 4 trường hợp sau: \(AATX,AATT,GATX,GATT\).

Cho trước gen của bố và gen của mẹ, bạn hãy viết chương trình liệt kê các khả năng có thể xảy ra của gen thế hệ con.

Input

  • Dòng thứ nhất: là số \(N\) biểu thị số ADN trong đoạn gen của bố và mẹ. (\(1 \le N \le 20\)).

  • Dòng thứ hai: đoạn gen của bố.

  • Dòng thứ ba: đoạn gen của mẹ. (hai đoạn gen này có chiều dài bằng \(N\) và chỉ gồm các ký tự \(A,X,T,G\)).

Output

  • Ghi số \(K\) là tổng số khả năng có thể xảy ra của đoạn gen thế hệ con.

Example

Test 1

Input
2
AT
GX
Output
4
Note

Sample input 1: Gen bố là \(AT\), gen mẹ là \(GX\), vậy khả năng gen của con là: \(AT,AX,TG,TX\).

Test 2

Input
3
AXT
GXA
Output
4

Bình luận


  • -4
    thanphong 11:34 p.m. 26 Tháng 2, 2022

    bài này thực chất chỉ cần 1 vòng for và tính các phần tử a[i]=b[i]

    sau đó tính 2^(n-dem) với dem là số phần tử a[i]=b[i] là xong toàn bài :>>

    1 phản hồi

    • -1
      huyhau6a2 9:25 p.m. 29 Tháng 12, 2021

      cái này mà cho n 1 triệu mới khó(kết quả mod 10^9+7)

      1 phản hồi